[lc-checkins] CVS: linux/mm/comp_cache Makefile,1.4,1.5 adaptivity.c,1.2,1.3 aux.c,1.9,1.10 free.c,1
Status: Beta
Brought to you by:
nitin_sf
Menu
▾
▴
[lc-checkins] CVS: linux/mm/comp_cache Makefile,1.4,1.5 adaptivity.c,1.2,1.3 aux.c,1.9,1.10 free.c,1.13,1.14 main.c,1.15,1.16 swapout.c,1.14,1.15 avl.c,1.3,NONE
|
From: Rodrigo S. de C. <rc...@us...> - 2002-01-07 17:48:33
|
Update of /cvsroot/linuxcompressed/linux/mm/comp_cache
In directory usw-pr-cvs1:/tmp/cvs-serv31165/mm/comp_cache
Modified Files:
Makefile adaptivity.c aux.c free.c main.c swapout.c
Removed Files:
avl.c
Log Message:
More changes regarding performance optimization.
- avl tree is finally removed. Now there's a new hash table for compressed
cache entries, what improved our cache performance. comp_cache_struct size
was decreased by 10 bytes with this change (actually 8 due to C struct
padding).
- search for duplicated fragments in get_comp_cache_page() was deleted since
it does not make sense any longer. Calls to _find_nolock_comp_page() have
fallen dramatically.
- comp_cache_notree() was renamed to comp_cache_nohash().
Index: Makefile
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/Makefile,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -r1.4 -r1.5
*** Makefile 2001/12/28 21:45:24 1.4
--- Makefile 2002/01/07 17:48:29 1.5
***************
*** 5,9 ****
O_TARGET := comp_cache.o
! obj-y := main.o vswap.o free.o swapout.o swapin.o adaptivity.o avl.o aux.o proc.o WK4x4.o WKdm.o
ifeq ($(CONFIG_COMP_SWAP),y)
--- 5,9 ----
O_TARGET := comp_cache.o
! obj-y := main.o vswap.o free.o swapout.o swapin.o adaptivity.o aux.o proc.o WK4x4.o WKdm.o
ifeq ($(CONFIG_COMP_SWAP),y)
Index: adaptivity.c
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/adaptivity.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -r1.2 -r1.3
*** adaptivity.c 2002/01/02 16:59:05 1.2
--- adaptivity.c 2002/01/07 17:48:29 1.3
***************
*** 2,6 ****
* linux/mm/comp_cache/adaptivity.c
*
! * Time-stamp: <2002-01-02 14:42:12 rcastro>
*
* Linux Virtual Memory Compressed Cache
--- 2,6 ----
* linux/mm/comp_cache/adaptivity.c
*
! * Time-stamp: <2002-01-07 11:18:58 rcastro>
*
* Linux Virtual Memory Compressed Cache
***************
*** 53,57 ****
check_empty_pages:
/* let's look for empty compressed cache entries */
! empty_comp_page = search_avl_tree_free_space(PAGE_SIZE);
if (!empty_comp_page)
--- 53,57 ----
check_empty_pages:
/* let's look for empty compressed cache entries */
! empty_comp_page = search_comp_page_free_space(PAGE_SIZE);
if (!empty_comp_page)
***************
*** 66,71 ****
}
! if (!avl_remove_free_space(empty_comp_page))
! BUG();
goto shrink;
--- 66,70 ----
}
! remove_comp_page_from_hash_table(empty_comp_page);
goto shrink;
Index: aux.c
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/aux.c,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -r1.9 -r1.10
*** aux.c 2002/01/04 22:24:07 1.9
--- aux.c 2002/01/07 17:48:29 1.10
***************
*** 2,6 ****
* linux/mm/comp_cache/aux.c
*
! * Time-stamp: <2002-01-04 19:10:26 rcastro>
*
* Linux Virtual Memory Compressed Cache
--- 2,6 ----
* linux/mm/comp_cache/aux.c
*
! * Time-stamp: <2002-01-07 14:44:05 rcastro>
*
* Linux Virtual Memory Compressed Cache
***************
*** 15,19 ****
--- 15,21 ----
comp_cache_fragment_t * fragment_hash[FRAGMENT_HASH_SIZE];
+ comp_cache_t * free_space_hash[FREE_SPACE_HASH_SIZE];
+
/* computes (unsigned long long x) / (unsigned long long y) */
unsigned long long
***************
*** 87,90 ****
--- 89,149 ----
inline void
+ add_comp_page_to_hash_table(comp_cache_t * new_comp_page) {
+ comp_cache_t ** comp_page;
+
+ comp_page = &free_space_hash[free_space_hashfn(new_comp_page->free_space)];
+
+ if ((new_comp_page->next_hash = *comp_page))
+ (*comp_page)->pprev_hash = &new_comp_page->next_hash;
+
+ *comp_page = new_comp_page;
+ new_comp_page->pprev_hash = comp_page;
+ }
+
+ inline void
+ remove_comp_page_from_hash_table(comp_cache_t * comp_page) {
+ comp_cache_t *next = comp_page->next_hash;
+ comp_cache_t **pprev = comp_page->pprev_hash;
+
+ if (next)
+ next->pprev_hash = pprev;
+ *pprev = next;
+ comp_page->pprev_hash = NULL;
+ }
+
+ comp_cache_t *
+ search_comp_page_free_space(int free_space) {
+ comp_cache_t * comp_page;
+ int idx, i;
+
+ idx = free_space_hashfn(free_space);
+
+ if (idx == FREE_SPACE_HASH_SIZE)
+ goto check_exact_size;
+
+ /* first of all let's try to get at once a comp page whose
+ * free space is surely bigger than what need */
+ i = idx + 1;
+ do {
+ comp_page = free_space_hash[i++];
+ } while(i < FREE_SPACE_HASH_SIZE && !comp_page);
+
+ /* couldn't find a page? let's check the pages whose free
+ * space is linked in our hash key entry */
+ if (!comp_page)
+ goto check_exact_size;
+
+ return comp_page;
+
+ check_exact_size:
+ comp_page = free_space_hash[idx];
+
+ while (comp_page && comp_page->free_space < free_space)
+ comp_page = comp_page->next_hash;
+
+ return comp_page;
+ }
+
+ inline void
add_fragment_to_lru_queue(comp_cache_fragment_t * fragment) {
swp_entry_t entry;
***************
*** 98,102 ****
return;
! list_add_tail(&(fragment->lru_queue), &lru_queue);
}
--- 157,161 ----
return;
! list_add(&(fragment->lru_queue), &lru_queue);
}
***************
*** 377,380 ****
--- 436,443 ----
for (i = 0; i < FRAGMENT_HASH_SIZE; i++)
fragment_hash[i] = NULL;
+
+ /* inits comp cache free space hash table */
+ for (i = 0; i < FREE_SPACE_HASH_SIZE; i++)
+ free_space_hash[i] = NULL;
}
Index: free.c
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/free.c,v
retrieving revision 1.13
retrieving revision 1.14
diff -C2 -r1.13 -r1.14
*** free.c 2002/01/02 16:59:05 1.13
--- free.c 2002/01/07 17:48:29 1.14
***************
*** 2,6 ****
* linux/mm/comp_cache/free.c
*
! * Time-stamp: <2001-12-31 12:38:32 rcastro>
*
* Linux Virtual Memory Compressed Cache
--- 2,6 ----
* linux/mm/comp_cache/free.c
*
! * Time-stamp: <2002-01-07 12:39:59 rcastro>
*
* Linux Virtual Memory Compressed Cache
***************
*** 32,36 ****
void
! comp_cache_free_notree(comp_cache_fragment_t * fragment_to_free)
{
comp_cache_t * comp_page = fragment_to_free->comp_page;
--- 32,36 ----
void
! comp_cache_free_nohash(comp_cache_fragment_t * fragment_to_free)
{
comp_cache_t * comp_page = fragment_to_free->comp_page;
***************
*** 156,164 ****
remove_fragment_from_lru_queue(fragment_to_free);
- /* let's null the index to make sure any old reference to this
- * fragment will fail when checking its index, like when
- * waiting for the comp_page->page lock in
- * swap_out_fragments */
- fragment_to_free->index = 0;
kmem_cache_free(fragment_cachep, (fragment_to_free));
--- 156,159 ----
***************
*** 186,199 ****
BUG();
! /* remove from avl tree, since we have to update its
! * free_space */
! if (!avl_remove_free_space(comp_page))
! BUG();
! comp_cache_free_notree(fragment);
/* steal the page if we need to shrink the comp cache */
! if (!shrink_comp_cache(comp_page)) {
! avl_insert_free_space(comp_page);
UnlockPage(comp_page->page);
}
--- 181,193 ----
BUG();
! /* remove from the free space hash table to update it */
! remove_comp_page_from_hash_table(comp_page);
! /* effectively free it */
! comp_cache_free_nohash(fragment);
/* steal the page if we need to shrink the comp cache */
! if (!shrink_comp_cache(comp_page)) {
! add_comp_page_to_hash_table(comp_page);
UnlockPage(comp_page->page);
}
Index: main.c
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/main.c,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -r1.15 -r1.16
*** main.c 2002/01/04 22:24:07 1.15
--- main.c 2002/01/07 17:48:29 1.16
***************
*** 2,6 ****
* linux/mm/comp_cache/main.c
*
! * Time-stamp: <2002-01-04 11:44:44 rcastro>
*
* Linux Virtual Memory Compressed Cache
--- 2,6 ----
* linux/mm/comp_cache/main.c
*
! * Time-stamp: <2002-01-07 11:44:08 rcastro>
*
* Linux Virtual Memory Compressed Cache
***************
*** 161,168 ****
PageSetCompCache((*comp_page)->page);
- INIT_LIST_HEAD(&((*comp_page)->avl_free_space.avl_list));
INIT_LIST_HEAD(&((*comp_page)->fragments));
!
! avl_insert_free_space((*comp_page));
}
--- 161,167 ----
PageSetCompCache((*comp_page)->page);
INIT_LIST_HEAD(&((*comp_page)->fragments));
!
! add_comp_page_to_hash_table((*comp_page));
}
***************
*** 183,187 ****
min_num_comp_pages = 0;
! printk("Starting compressed cache v0.21pre2 (%lu pages = %luk)\n", max_num_comp_pages, (max_num_comp_pages * PAGE_SIZE)/1024);
/* initialize our data for the `test' compressed_page */
--- 182,186 ----
min_num_comp_pages = 0;
! printk("Starting compressed cache v0.21pre4 (%lu pages = %luk)\n", max_num_comp_pages, (max_num_comp_pages * PAGE_SIZE)/1024);
/* initialize our data for the `test' compressed_page */
***************
*** 207,213 ****
comp_cache_vswap_init();
- /* avl tree */
- comp_avl_free_space = NULL;
-
/* initialize each comp cache entry */
for (i = 0; i < real_num_comp_pages; i++) {
--- 206,209 ----
Index: swapout.c
===================================================================
RCS file: /cvsroot/linuxcompressed/linux/mm/comp_cache/swapout.c,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -r1.14 -r1.15
*** swapout.c 2002/01/04 22:24:07 1.14
--- swapout.c 2002/01/07 17:48:29 1.15
***************
*** 2,6 ****
* linux/mm/comp_cache/swapout.c
*
! * Time-stamp: <2002-01-03 17:24:51 rcastro>
*
* Linux Virtual Memory Compressed Cache
--- 2,6 ----
* linux/mm/comp_cache/swapout.c
*
! * Time-stamp: <2002-01-07 15:33:19 rcastro>
*
* Linux Virtual Memory Compressed Cache
***************
*** 158,162 ****
while (!list_empty(&lru_queue) && maxscan--) {
! fragment = list_entry(fragment_lh = lru_queue.next, comp_cache_fragment_t, lru_queue);
entry.val = fragment->index;
--- 158,162 ----
while (!list_empty(&lru_queue) && maxscan--) {
! fragment = list_entry(fragment_lh = lru_queue.prev, comp_cache_fragment_t, lru_queue);
entry.val = fragment->index;
***************
*** 190,194 ****
if (TryLockPage(page)) {
list_del(fragment_lh);
! list_add_tail(fragment_lh, &lru_queue);
maxscan++;
goto freed;
--- 190,194 ----
if (TryLockPage(page)) {
list_del(fragment_lh);
! list_add(fragment_lh, &lru_queue);
maxscan++;
goto freed;
***************
*** 252,256 ****
}
! extern void comp_cache_free_notree(comp_cache_fragment_t *);
/**
--- 252,256 ----
}
! extern void comp_cache_free_nohash(comp_cache_fragment_t *);
/**
***************
*** 269,274 ****
{
struct list_head * fragment_lh = NULL, * temp_lh;
! comp_cache_t * comp_page = NULL, * dup_comp_page;
! comp_cache_fragment_t * fragment = NULL, * dup_fragment;
swp_entry_t entry;
unsigned short aux_comp_size;
--- 269,274 ----
{
struct list_head * fragment_lh = NULL, * temp_lh;
! comp_cache_t * comp_page = NULL;
! comp_cache_fragment_t * fragment = NULL;
swp_entry_t entry;
unsigned short aux_comp_size;
***************
*** 295,299 ****
while (maxscan--) {
! comp_page = search_avl_tree_free_space(aux_comp_size);
/* no comp_page, that comp_page->free_space > compressed_size */
--- 295,299 ----
while (maxscan--) {
! comp_page = search_comp_page_free_space(aux_comp_size);
/* no comp_page, that comp_page->free_space > compressed_size */
***************
*** 316,322 ****
}
! /* remove from AVL tree before updating */
! if (!avl_remove_free_space(comp_page))
! BUG();
if (comp_page->free_space < compressed_size)
--- 316,321 ----
}
! /* remove from free space hash table before update */
! remove_comp_page_from_hash_table(comp_page);
if (comp_page->free_space < compressed_size)
***************
*** 353,358 ****
new_page:
! /* remove from AVL tree before updating*/
! avl_remove_free_space(comp_page);
if (comp_page->page)
--- 352,357 ----
new_page:
! /* remove from free space hash table before update */
! remove_comp_page_from_hash_table(comp_page);
if (comp_page->page)
***************
*** 386,390 ****
* */
if (mapped(swap_cache_page)) {
! avl_insert_free_space(comp_page);
UnlockPage(comp_page->page);
return NULL;
--- 385,389 ----
* */
if (mapped(swap_cache_page)) {
! add_comp_page_to_hash_table(comp_page);
UnlockPage(comp_page->page);
return NULL;
***************
*** 394,418 ****
BUG();
- /* before messing up the page, let's make sure there's other
- * fragment with this entry. It can happen to be other
- * compressed page with this entry, since we may have had a
- * swap cache page with page_count > 2 (linus if clause
- * above), we have cleaned it and later it has been dirtied
- * again (since it may have returned to active list) */
- dup_comp_page = find_nolock_comp_page((swp_entry_t) { swap_cache_page->index }, &dup_fragment);
-
- /* there is another fragment, that should never happen */
- if (dup_comp_page) {
- /* the fragment is in this comp_page or we couldn't lock it */
- if (dup_comp_page == comp_page || TryLockPage(dup_comp_page->page)) {
- if (CompFragmentTestandSetFreed(dup_fragment))
- BUG();
-
- goto update_fragment;
- }
-
- comp_cache_free(dup_fragment);
- }
-
update_fragment:
/* free any freed fragments in this comp_page */
--- 393,396 ----
***************
*** 421,425 ****
if (CompFragmentFreed(fragment))
! comp_cache_free_notree(fragment);
}
--- 399,403 ----
if (CompFragmentFreed(fragment))
! comp_cache_free_nohash(fragment);
}
***************
*** 471,475 ****
*fragment_out = fragment;
! avl_insert_free_space(comp_page);
if ((*fragment_out)->compressed_size != compressed_size)
--- 449,453 ----
*fragment_out = fragment;
! add_comp_page_to_hash_table(comp_page);
if ((*fragment_out)->compressed_size != compressed_size)
--- avl.c DELETED ---
|
