Memory file size adjustment
View Patent ↗Shrinking a database file is performed by manipulating pages within the file such that all empty pages reside at the end of the file. Non-empty pages from the end of the file are written to empty pages at the start of the file. Repeating this process, the correct number of times, results in all of the empty pages residing at the end of the file. Once this is achieved, the file is truncated such that the space consumed by all empty and discardable pages is returned to the file system. Truncating the file involves traversing the file backwards from the end of the file until the first non-empty page is found. The file is truncated after the last non-empty page.
1. A method for adjusting a size of a file having a total number of empty pages, said method comprising:
(a) starting a traversal of said file at a last page of said file and progressing toward a first page of said file;
(b) indicating an encountered page as skipped if said encountered page is empty;
(c) indicating said encountered page as dirty if said encountered page is non-empty;
(d) subsequent to acts (b) and (c), comparing a sum of skipped pages plus dirty pages to the total number of empty pages in said file;
if said sum is less than said total number of empty pages, traversing said file to a next page and performing acts (b), (c), and (d);
if said sum is greater than or equal to said total number of empty pages:
writing contents of said dirty pages to empty pages of said file that have not been traversed; and
indicating each dirty page and each skipped page as unallocated; and truncating said unallocated pages from said file.
2. A method in accordance with claim 1 , further comprising:
determining if a percentage of empty pages of said file with respect to a total number of pages of said file is greater than or equal to an empty page threshold;
if said percentage is greater than or equal to said empty page threshold, starting said traversal of said file.
3. A method in accordance with claim 1 , wherein:
dirty pages are written to said empty pages starting with a dirty page closest to said last page of said file and progressing toward said first page of said file.
4. A method in accordance with claim 1 , further comprising:
determining if a maximum execution time has elapsed since starting said traversal; and
if said maximum execution time has elapsed, commencing said acts of:
writing contents of said dirty pages to empty pages of said file that have not been traversed;
indicating each dirty page and each skipped page as unallocated; and
truncating said unallocated pages from said file.
5. A method in accordance with claim 1 , further comprising:
generating a bitmap for indicating allocation status of each dirty page and each skipped page; and
updating said bitmap in accordance with said act of indicating each dirty page and each skipped page as unallocated.
6. A method in accordance with claim 1 , further comprising:
determining a total number of pages in said file;
determining a number of empty pages in said file;
determining a percent of empty pages with respect to said total number of pages;
comparing a value of said percent with an empty page threshold value;
if said percent is greater than or equal to said empty page threshold:
starting a traversal of said file at a last page of said file and progressing toward a first page of said file;
(i) indicating an encountered page as skipped if said encountered page is empty;
(ii) indicating said encountered page as dirty if said encountered page is non-empty;
(ii) comparing a sum of skipped pages plus dirty pages to said number of empty pages;
if said sum is less than said number of empty pages, traversing said file to a next page and performing acts (i), (ii), and (iii); and
if said sum is greater than or equal to said number of empty pages:
writing contents of said dirty pages to empty pages of said file that have not been traversed; and
indicating each dirty page and each skipped paged as unallocated.
7. A method for adjusting a size of a file, said method comprising:
determining a total number of pages in said file;
determining a number of empty pages in said file;
determining a percent of empty pages with respect to said total number of pages;
comparing a value of said percent with an empty page threshold value;
if said percent value is greater than or equal to said empty page threshold:
starting a traversal of said file at a last page of said file and progressing toward a first page of said file;
(a) indicating an encountered page as skipped if said encountered page is empty;
(b) indicating said encountered page as dirty if said encountered page is non-empty;
(c) subsequent to acts (a) and (b), comparing a sum of skipped pages plus dirty pages to said number of empty pages;
if said sum is less than said number of empty pages, traversing said file to a next page and performing acts (a), (b), and (c);
if said sum is greater than or equal to said number of empty pages:
writing contents of said dirty pages to empty pages of said file that have not been traversed; and
indicating each dirty page and each skipped page as unallocated; and
truncating said unallocated pages from said file.
8. A computer readable medium encoded with a computer program code for directing a computer processor to adjust memory size having a total number of empty pages, said program comprising:
a start code segment for causing said computer processor to (a) start a traversal of a file of said memory at a last page of said file and progressing toward a first page of said file;
an indicate skipped code segment for causing said computer to (b) indicate an encountered page as skipped if said encountered page is empty;
an indicate dirty code segment for causing said computer to (c) indicate said encountered page as dirty if said encountered page is non-empty;
a compare code segment for, subsequent to acts (b) and (c), causing said computer to (d) compare a sum of skipped pages plus dirty pages to the total number of empty pages in said file;
a next page code segment for causing said computer processor to, if said sum is less than said total number of empty pages, traverse said file to a next page and performing acts (b), (c), and (d);
a sum greater than code segment for causing a computer processor to, if said sum is greater than or equal to said total number of empty pages:
write contents of said dirty pages to empty pages of said file that have not been traversed; and
indicate each dirty page and each skipped page as unallocated; and
a truncate code segment for causing said computer processor to truncate said unallocated pages from said file.
9. A computer readable medium in accordance with claim 8 , further comprising:
a percentage code segment for causing said computer processor to determine if a percentage of empty pages of said file with respect to a total number of pages of said file is greater than or equal to an empty page threshold;
a conditional start code segment for causing said computer processor to, if said percentage is greater than or equal to said empty page threshold, start said traversal of said file.
10. A computer readable medium in accordance with claim 8 , wherein:
dirty pages are written to said empty pages starting with a dirty page closest to said last page of said file and progressing toward said first page of said file.
11. A computer readable medium in accordance with claim 8 , further comprising:
a determine maximum time code segment for causing said computer processor to determine if a maximum execution time has elapsed since starting said traversal; and
a conditional commence code segment for causing said computer processor to, if said maximum execution time has elapsed, commence said acts of:
writing contents of said dirty pages to empty pages of said file that have not been traversed;
indicating each dirty page and each skipped page as unallocated; and
truncating said unallocated pages from said file.
12. A computer readable medium in accordance with claim 8 , further comprising:
a generate bitmap code segment for causing said computer processor to generate a bitmap for indicating allocation status of each dirty page and each skipped page; and
a update bitmap code segment for causing said computer processor to update said bitmap in accordance with said act of indicating each dirty page and each skipped page as unallocated.
13. A system for adjusting memory size, said system comprising:
a memory file comprising pages;
a controller for starting a traversal of said file at a last page of said file and progressing toward a first page of said file, and for each page encountered during said traversal, the controller performing acts comprising:
indicating an encountered page as skipped if said encountered page is empty;
indicating said encountered page as dirty if said encountered page is non-empty;
subsequent to the acts of indicating an encountered page as skipped if said encountered page is empty and indicating said encountered page as dirty if said encountered page is non-empty, comparing a sum of skipped pages pIus dirty pages to a predetermined total number of empty pages in said file;
if said sum is less than said predetermined total number of empty pages, continuing said traversal at a next page in said file in traversal order; and
if said sum is greater than or equal to said predetermined total number of empty pages, writing contents of said dirty pages to empty pages of said file that have not been traversed;
an allocation indicator for indicating each dirty page and each skipped page as unallocated; and
a truncator or truncating said unallocated pages from said file.
14. A system in accordance with claim 13 , wherein said controller further:
determines if a percentage of empty pages of said file with respect to a total number of pages of said file is greater than or equal to an empty page threshold;
if said percentage is greater than or equal to said empty page threshold, starts said traversal of said file.
15. A system in accordance with claim 13 , wherein:
dirty pages are written to said empty pages starting with a dirty page closest to said last page of said file and progressing toward said first page of said file.
16. A system in accordance with claim 13 , said controller further:
determines if a maximum execution time has elapsed since starting said traversal; and
if said maximum execution time has elapsed, commences:
writing contents of said dirty pages to empty pages of said file that have not been traversed;
indicating each dirty page and each skipped page as unallocated; and
truncating said unallocated pages from said file.
17. A system in accordance with claim 13 , wherein:
said allocation indicator comprises a bitmap for indicating allocation status of each dirty page and each skipped page; and
said controller updates said bitmap in accordance with said act of indicating each dirty page and each skipped page as unallocated.