Re: Memory Problem in 2.4.10-pre2 / __alloc_pages failed

[Daniel Phillips]

Reposted to include Alex's correction.  Alex, could you please check this?

On September 2, 2001 09:32 pm, Alex Bligh - linux-kernel wrote:
> IDEA: Attempt not to allocate sets of pages buddied with 'nearly
> free' sets of pages.
> 
> When freeing pages, we work our way up the orders until
> we find a buddy which is non-empty. Let's assume that
> the free area, and our (non-empty) buddy, are of order N.
> Let's look at whether at order N-1, it's merely half full,
> or completely full. If completely full, we guess that
> the buddy is unlikely to become free soon, and thus
> add our area to the front of the memory queue (mem_add_head)
> else we guess it's more likely to have its buddy freed
> and add it to the back of the memory queue (mem_add_tail).
> 
> /Completely/ untested (i.e. uncompiled) patch attached

Rediffed to 2.4.9, whitespace and wrapping problems fixed, and compiled
but not tested.  Now we just need a victi^H^H^H^H^H volunteer to try it...
(Stephan?)

--- ../2.4.9.clean/mm/page_alloc.c	Thu Aug 16 12:43:02 2001
+++ ./mm/page_alloc.c	Sun Sep  2 21:09:05 2001
@@ -69,6 +69,8 @@
 	struct page *base;
 	zone_t *zone;
 
+       int addfront=1;
+
 	if (page->buffers)
 		BUG();
 	if (page->mapping)
@@ -112,10 +114,22 @@
 		if (area >= zone->free_area + MAX_ORDER)
 			BUG();
 		if (!__test_and_change_bit(index, area->map))
-			/*
-			 * the buddy page is still allocated.
-			 */
-			break;
+                 {
+                   /*
+                    * the buddy page is still allocated.
+                    *
+                    * see how many bits are set in its bitmap;
+                    * if 50% or more, we conclude the buddy is
+                    * unlikely to be freed soon, and add the
+                    * area to the head of the queue; else we
+                    * conclude the buddy may be free soon and
+                    * add it to the head.
+                    */
+                   if (mask & 1) /* not order 0 merge */
+                     addfront = ( !test_bit((index^1)<<1, (area-1)->map) &&
+                                  !test_bit(((index^1)<<1) | 1, (area-1)->map) );
+                   break;
+                 }
 		/*
 		 * Move the buddy up one level.
 		 */
@@ -132,7 +146,11 @@
 		index >>= 1;
 		page_idx &= mask;
 	}
-	memlist_add_head(&(base + page_idx)->list, &area->free_list);
+
+       if (addfront)
+         memlist_add_head(&(base + page_idx)->list, &area->free_list);
+       else
+         memlist_add_tail(&(base + page_idx)->list, &area->free_list);
 
 	spin_unlock_irqrestore(&zone->lock, flags);