Skip to contentSkip to conversation

mini-os: cleanup of mm.c

PATCH In review Juergen Gross 2 participants 14 messages Jul 22, 2024 – Jul 25, 2024

lore
Share & tools
lore
#0 lore raw

cover mini-os: cleanup of mm.c

Some cleanups in mm.c: style, removal of unused stuff, optimizations.

Juergen Gross (4):
mini-os: make mm.c coding style compliant
mini-os: mm: remove not needed struct chunk_tail_st
mini-os: mm: reduce buddy allocator list administration data
mini-os: remove sanity_check()

 include/lib.h |   3 -
 mm.c          | 264 +++++++++++++++++++++-----------------------------
 2 files changed, 112 insertions(+), 155 deletions(-)
Signature · 1 line
2.43.0
#1 lore raw

PATCH 1/4 mini-os: make mm.c coding style compliant

Apply the coding style to mm.c.

No functional change.

---
 mm.c | 191 ++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 96 insertions(+), 95 deletions(-)
mm.c +96 -95
index eb0e34de..1dcd954c 100644
@@ -1,4 +1,4 @@
-/* 
+/*
  ****************************************************************************
  * (C) 2003 - Rolf Neugebauer - Intel Research Cambridge
  * (C) 2005 - Grzegorz Milos - Intel Research Cambridge
@@ -7,9 +7,9 @@
  *        File: mm.c
  *      Author: Rolf Neugebauer ([email protected])
  *     Changes: Grzegorz Milos
- *              
+ *
  *        Date: Aug 2003, chages Aug 2005
- * 
+ *
  * Environment: Xen Minimal OS
  * Description: memory management related functions
  *              contains buddy page allocator from Xen.
@@ -21,16 +21,16 @@
  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  * sell copies of the Software, and to permit persons to whom the Software is
  * furnished to do so, subject to the following conditions:
- * 
+ *
  * The above copyright notice and this permission notice shall be included in
  * all copies or substantial portions of the Software.
- * 
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  * DEALINGS IN THE SOFTWARE.
  */
 
@@ -45,7 +45,7 @@
 #include <mini-os/xmalloc.h>
 #include <mini-os/e820.h>
 
-/*********************
+/*
  * ALLOCATION BITMAP
  *  One bit per page of memory. Bit set => page is allocated.
  */
@@ -55,7 +55,7 @@ unsigned long mm_alloc_bitmap_size;
 
 #define PAGES_PER_MAPWORD (sizeof(unsigned long) * 8)
 
-#define allocated_in_map(_pn) \
+#define allocated_in_map(_pn)                     \
     (mm_alloc_bitmap[(_pn) / PAGES_PER_MAPWORD] & \
      (1UL << ((_pn) & (PAGES_PER_MAPWORD - 1))))
 
@@ -63,8 +63,8 @@ unsigned long nr_free_pages;
 
 /*
  * Hint regarding bitwise arithmetic in map_{alloc,free}:
- *  -(1<<n)  sets all bits >= n. 
- *  (1<<n)-1 sets all bits <  n.
+ *  -(1 << n)  sets all bits >= n.
+ *  (1 << n) - 1 sets all bits <  n.
  * Variable names in map_{alloc,free}:
  *  *_idx == Index into `mm_alloc_bitmap' array.
  *  *_off == Bit offset within an element of the `mm_alloc_bitmap' array.
@@ -75,53 +75,52 @@ static void map_alloc(unsigned long first_page, unsigned long nr_pages)
     unsigned long start_off, end_off, curr_idx, end_idx;
 
     curr_idx  = first_page / PAGES_PER_MAPWORD;
-    start_off = first_page & (PAGES_PER_MAPWORD-1);
+    start_off = first_page & (PAGES_PER_MAPWORD - 1);
     end_idx   = (first_page + nr_pages) / PAGES_PER_MAPWORD;
-    end_off   = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
+    end_off   = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
 
     if ( curr_idx == end_idx )
     {
-        mm_alloc_bitmap[curr_idx] |= ((1UL<<end_off)-1) & -(1UL<<start_off);
+        mm_alloc_bitmap[curr_idx] |= ((1UL << end_off) - 1) &
+                                     -(1UL << start_off);
     }
-    else 
+    else
     {
-        mm_alloc_bitmap[curr_idx] |= -(1UL<<start_off);
-        while ( ++curr_idx < end_idx ) mm_alloc_bitmap[curr_idx] = ~0UL;
-        mm_alloc_bitmap[curr_idx] |= (1UL<<end_off)-1;
+        mm_alloc_bitmap[curr_idx] |= -(1UL << start_off);
+        while ( ++curr_idx < end_idx )
+            mm_alloc_bitmap[curr_idx] = ~0UL;
+        mm_alloc_bitmap[curr_idx] |= (1UL << end_off) - 1;
     }
 
     nr_free_pages -= nr_pages;
 }
 
-
 static void map_free(unsigned long first_page, unsigned long nr_pages)
 {
     unsigned long start_off, end_off, curr_idx, end_idx;
 
     curr_idx = first_page / PAGES_PER_MAPWORD;
-    start_off = first_page & (PAGES_PER_MAPWORD-1);
+    start_off = first_page & (PAGES_PER_MAPWORD - 1);
     end_idx   = (first_page + nr_pages) / PAGES_PER_MAPWORD;
-    end_off   = (first_page + nr_pages) & (PAGES_PER_MAPWORD-1);
+    end_off   = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
 
     nr_free_pages += nr_pages;
 
     if ( curr_idx == end_idx )
     {
-        mm_alloc_bitmap[curr_idx] &= -(1UL<<end_off) | ((1UL<<start_off)-1);
+        mm_alloc_bitmap[curr_idx] &= -(1UL << end_off) |
+                                     ((1UL << start_off) - 1);
     }
-    else 
+    else
     {
-        mm_alloc_bitmap[curr_idx] &= (1UL<<start_off)-1;
-        while ( ++curr_idx != end_idx ) mm_alloc_bitmap[curr_idx] = 0;
-        mm_alloc_bitmap[curr_idx] &= -(1UL<<end_off);
+        mm_alloc_bitmap[curr_idx] &= (1UL << start_off) - 1;
+        while ( ++curr_idx != end_idx )
+            mm_alloc_bitmap[curr_idx] = 0;
+        mm_alloc_bitmap[curr_idx] &= -(1UL << end_off);
     }
 }
 
-
-
-/*************************
- * BINARY BUDDY ALLOCATOR
- */
+/* BINARY BUDDY ALLOCATOR */
 
 typedef struct chunk_head_st chunk_head_t;
 typedef struct chunk_tail_st chunk_tail_t;
@@ -137,7 +136,7 @@ struct chunk_tail_st {
 };
 
 /* Linked lists of free chunks of different powers-of-two in size. */
-#define FREELIST_SIZE ((sizeof(void*)<<3)-PAGE_SHIFT)
+#define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT)
 static chunk_head_t *free_head[FREELIST_SIZE];
 static chunk_head_t  free_tail[FREELIST_SIZE];
 #define FREELIST_EMPTY(_l) ((_l)->next == NULL)
@@ -163,14 +162,14 @@ static void init_page_allocator(unsigned long min, unsigned long max)
         free_tail[i].next  = NULL;
     }
 
-    min = round_pgup  (min);
+    min = round_pgup(min);
     max = round_pgdown(max);
 
     /* Allocate space for the allocation bitmap. */
-    mm_alloc_bitmap_size  = (max + 1) >> (PAGE_SHIFT + 3);
-    mm_alloc_bitmap_size  = round_pgup(mm_alloc_bitmap_size);
+    mm_alloc_bitmap_size = (max + 1) >> (PAGE_SHIFT + 3);
+    mm_alloc_bitmap_size = round_pgup(mm_alloc_bitmap_size);
     mm_alloc_bitmap = (unsigned long *)to_virt(min);
-    min         += mm_alloc_bitmap_size;
+    min += mm_alloc_bitmap_size;
 
     /* All allocated by default. */
     memset(mm_alloc_bitmap, ~0, mm_alloc_bitmap_size);
@@ -208,7 +207,10 @@ static void init_page_allocator(unsigned long min, unsigned long max)
              * must not be bigger than remaining range.
              */
             for ( i = PAGE_SHIFT; (1UL << (i + 1)) <= range; i++ )
-                if ( r_min & (1UL << i) ) break;
+            {
+                if ( r_min & (1UL << i) )
+                    break;
+            }
 
             ch = (chunk_head_t *)r_min;
             r_min += 1UL << i;
@@ -227,7 +229,6 @@ static void init_page_allocator(unsigned long min, unsigned long max)
     mm_alloc_bitmap_remap();
 }
 
-
 /* Allocate 2^@order contiguous pages. Returns a VIRTUAL address. */
 unsigned long alloc_pages(int order)
 {
@@ -239,13 +240,15 @@ unsigned long alloc_pages(int order)
         goto no_memory;
 
     /* Find smallest order which can satisfy the request. */
-    for ( i = order; i < FREELIST_SIZE; i++ ) {
-	if ( !FREELIST_EMPTY(free_head[i]) ) 
-	    break;
+    for ( i = order; i < FREELIST_SIZE; i++ )
+    {
+        if ( !FREELIST_EMPTY(free_head[i]) )
+            break;
     }
 
-    if ( i == FREELIST_SIZE ) goto no_memory;
- 
+    if ( i == FREELIST_SIZE )
+        goto no_memory;
+
     /* Unlink a chunk. */
     alloc_ch = free_head[i];
     free_head[i] = alloc_ch->next;
@@ -256,8 +259,10 @@ unsigned long alloc_pages(int order)
     {
         /* Split into two equal parts. */
         i--;
-        spare_ch = (chunk_head_t *)((char *)alloc_ch + (1UL<<(i+PAGE_SHIFT)));
-        spare_ct = (chunk_tail_t *)((char *)spare_ch + (1UL<<(i+PAGE_SHIFT)))-1;
+        spare_ch = (chunk_head_t *)((char *)alloc_ch +
+                                    (1UL << (i + PAGE_SHIFT)));
+        spare_ct = (chunk_tail_t *)((char *)spare_ch +
+                                    (1UL << (i + PAGE_SHIFT))) - 1;
 
         /* Create new header for spare chunk. */
         spare_ch->level = i;
@@ -269,13 +274,12 @@ unsigned long alloc_pages(int order)
         spare_ch->next->pprev = &spare_ch->next;
         free_head[i] = spare_ch;
     }
-    
-    map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1UL<<order);
 
-    return((unsigned long)alloc_ch);
+    map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1UL << order);
 
- no_memory:
+    return (unsigned long)alloc_ch;
 
+ no_memory:
     printk("Cannot handle page request order %d!\n", order);
 
     return 0;
@@ -287,43 +291,44 @@ void free_pages(void *pointer, int order)
     chunk_head_t *freed_ch, *to_merge_ch;
     chunk_tail_t *freed_ct;
     unsigned long mask;
-    
+
     /* First free the chunk */
     map_free(virt_to_pfn(pointer), 1UL << order);
-    
+
     /* Create free chunk */
     freed_ch = (chunk_head_t *)pointer;
-    freed_ct = (chunk_tail_t *)((char *)pointer + (1UL<<(order + PAGE_SHIFT)))-1;
-    
+    freed_ct = (chunk_tail_t *)((char *)pointer +
+                                (1UL << (order + PAGE_SHIFT))) - 1;
+
     /* Now, possibly we can conseal chunks together */
-    while(order < FREELIST_SIZE)
+    while ( order < FREELIST_SIZE )
     {
         mask = 1UL << (order + PAGE_SHIFT);
-        if((unsigned long)freed_ch & mask) 
+        if ( (unsigned long)freed_ch & mask )
         {
             to_merge_ch = (chunk_head_t *)((char *)freed_ch - mask);
-            if(allocated_in_map(virt_to_pfn(to_merge_ch)) ||
-                    to_merge_ch->level != order)
+            if ( allocated_in_map(virt_to_pfn(to_merge_ch)) ||
+                 to_merge_ch->level != order )
                 break;
-            
+
             /* Merge with predecessor */
-            freed_ch = to_merge_ch;   
+            freed_ch = to_merge_ch;
         }
-        else 
+        else
         {
             to_merge_ch = (chunk_head_t *)((char *)freed_ch + mask);
-            if(allocated_in_map(virt_to_pfn(to_merge_ch)) ||
-                    to_merge_ch->level != order)
+            if ( allocated_in_map(virt_to_pfn(to_merge_ch)) ||
+                 to_merge_ch->level != order )
                 break;
-            
+
             /* Merge with successor */
             freed_ct = (chunk_tail_t *)((char *)to_merge_ch + mask) - 1;
         }
-        
-        /* We are commited to merging, unlink the chunk */
+
+        /* We are committed to merging, unlink the chunk */
         *(to_merge_ch->pprev) = to_merge_ch->next;
         to_merge_ch->next->pprev = to_merge_ch->pprev;
-        
+
         order++;
     }
 
@@ -332,10 +337,10 @@ void free_pages(void *pointer, int order)
     freed_ch->next  = free_head[order];
     freed_ch->pprev = &free_head[order];
     freed_ct->level = order;
-    
+
     freed_ch->next->pprev = &freed_ch->next;
-    free_head[order] = freed_ch;   
-   
+    free_head[order] = freed_ch;
+
 }
 EXPORT_SYMBOL(free_pages);
 
@@ -347,6 +352,7 @@ int free_physical_pages(xen_pfn_t *mfns, int n)
     reservation.nr_extents = n;
     reservation.extent_order = 0;
     reservation.domid = DOMID_SELF;
+
     return HYPERVISOR_memory_op(XENMEM_decrease_reservation, &reservation);
 }
 
@@ -362,16 +368,15 @@ void *sbrk(ptrdiff_t increment)
     unsigned long old_brk = brk;
     unsigned long new_brk = old_brk + increment;
 
-    if (new_brk > heap_end) {
-	printk("Heap exhausted: %lx + %lx = %p > %p\n",
-			old_brk,
-			(unsigned long) increment,
-			(void *) new_brk,
-			(void *) heap_end);
-	return NULL;
+    if ( new_brk > heap_end )
+    {
+        printk("Heap exhausted: %lx + %lx = %p > %p\n", old_brk,
+               (unsigned long) increment, (void *)new_brk, (void *)heap_end);
+        return NULL;
     }
-    
-    if (new_brk > heap_mapped) {
+
+    if ( new_brk > heap_mapped )
+    {
         unsigned long n = (new_brk - heap_mapped + PAGE_SIZE - 1) / PAGE_SIZE;
 
         if ( !chk_free_pages(n) )
@@ -386,16 +391,13 @@ void *sbrk(ptrdiff_t increment)
 
     brk = new_brk;
 
-    return (void *) old_brk;
+    return (void *)old_brk;
 }
 EXPORT_SYMBOL(sbrk);
 #endif
 
-
-
 void init_mm(void)
 {
-
     unsigned long start_pfn, max_pfn;
 
     printk("MM: Init\n");
@@ -403,14 +405,12 @@ void init_mm(void)
     arch_init_mm(&start_pfn, &max_pfn);
     get_max_pages();
 
-    /*
-     * now we can initialise the page allocator
-     */
+    /* Now we can initialise the page allocator. */
     init_page_allocator(PFN_PHYS(start_pfn), PFN_PHYS(max_pfn));
     printk("MM: done\n");
 
     arch_init_p2m(max_pfn);
-    
+
     arch_init_demand_mapping_area();
 }
 
@@ -423,14 +423,15 @@ void sanity_check(void)
     int x;
     chunk_head_t *head;
 
-    for (x = 0; x < FREELIST_SIZE; x++) {
-        for (head = free_head[x]; !FREELIST_EMPTY(head); head = head->next) {
+    for ( x = 0; x < FREELIST_SIZE; x++ )
+    {
+        for ( head = free_head[x]; !FREELIST_EMPTY(head); head = head->next )
+        {
             ASSERT(!allocated_in_map(virt_to_pfn(head)));
-            if (head->next)
+            if ( head->next )
                 ASSERT(head->next->pprev == &head->next);
         }
-        if (free_head[x]) {
+        if ( free_head[x] )
             ASSERT(free_head[x]->pprev == &free_head[x]);
-        }
     }
 }
Signature · 1 line
2.43.0
Reviewed-by on v1 1/4
#2 lore raw

Re: [PATCH 1/4] mini-os: make mm.c coding style compliant

Juergen Gross, le lun. 22 juil. 2024 17:01:38 +0200, a ecrit:

mm.c unsigned long nr_free_pages; · line 67

Quoted 8 lines
mm.c +2 -2
@@ -63,8 +63,8 @@ unsigned long nr_free_pages;
 
 /*
  * Hint regarding bitwise arithmetic in map_{alloc,free}:
- *  -(1<<n)  sets all bits >= n. 
- *  (1<<n)-1 sets all bits <  n.
+ *  -(1 << n)  sets all bits >= n.
+ *  (1 << n) - 1 sets all bits <  n.

Please keep the alignment of "sets"

Apart this nitpick,

Samuel

#3 lore raw

PATCH 2/4 mini-os: mm: remove not needed struct chunk_tail_st

In reply to Juergen Gross

The struct chunk_tail_st isn't really used other than writing to it.

Remove it in order to simplify the code.

---
 mm.c | 20 --------------------
 1 file changed, 20 deletions(-)
mm.c +0 -20
index 1dcd954c..2cc49e94 100644
@@ -123,7 +123,6 @@ static void map_free(unsigned long first_page, unsigned long nr_pages)
 /* BINARY BUDDY ALLOCATOR */
 
 typedef struct chunk_head_st chunk_head_t;
-typedef struct chunk_tail_st chunk_tail_t;
 
 struct chunk_head_st {
     chunk_head_t  *next;
@@ -131,10 +130,6 @@ struct chunk_head_st {
     int            level;
 };
 
-struct chunk_tail_st {
-    int level;
-};
-
 /* Linked lists of free chunks of different powers-of-two in size. */
 #define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT)
 static chunk_head_t *free_head[FREELIST_SIZE];
@@ -151,7 +146,6 @@ static void init_page_allocator(unsigned long min, unsigned long max)
     unsigned long range;
     unsigned long r_min, r_max;
     chunk_head_t *ch;
-    chunk_tail_t *ct;
 
     printk("MM: Initialise page allocator for %lx(%lx)-%lx(%lx)\n",
            (u_long)to_virt(min), min, (u_long)to_virt(max), max);
@@ -215,14 +209,12 @@ static void init_page_allocator(unsigned long min, unsigned long max)
             ch = (chunk_head_t *)r_min;
             r_min += 1UL << i;
             range -= 1UL << i;
-            ct = (chunk_tail_t *)r_min - 1;
             i -= PAGE_SHIFT;
             ch->level       = i;
             ch->next        = free_head[i];
             ch->pprev       = &free_head[i];
             ch->next->pprev = &ch->next;
             free_head[i]    = ch;
-            ct->level       = i;
         }
     }
 
@@ -234,7 +226,6 @@ unsigned long alloc_pages(int order)
 {
     int i;
     chunk_head_t *alloc_ch, *spare_ch;
-    chunk_tail_t            *spare_ct;
 
     if ( !chk_free_pages(1UL << order) )
         goto no_memory;
@@ -261,14 +252,11 @@ unsigned long alloc_pages(int order)
         i--;
         spare_ch = (chunk_head_t *)((char *)alloc_ch +
                                     (1UL << (i + PAGE_SHIFT)));
-        spare_ct = (chunk_tail_t *)((char *)spare_ch +
-                                    (1UL << (i + PAGE_SHIFT))) - 1;
 
         /* Create new header for spare chunk. */
         spare_ch->level = i;
         spare_ch->next  = free_head[i];
         spare_ch->pprev = &free_head[i];
-        spare_ct->level = i;
 
         /* Link in the spare chunk. */
         spare_ch->next->pprev = &spare_ch->next;
@@ -289,7 +277,6 @@ EXPORT_SYMBOL(alloc_pages);
 void free_pages(void *pointer, int order)
 {
     chunk_head_t *freed_ch, *to_merge_ch;
-    chunk_tail_t *freed_ct;
     unsigned long mask;
 
     /* First free the chunk */
@@ -297,8 +284,6 @@ void free_pages(void *pointer, int order)
 
     /* Create free chunk */
     freed_ch = (chunk_head_t *)pointer;
-    freed_ct = (chunk_tail_t *)((char *)pointer +
-                                (1UL << (order + PAGE_SHIFT))) - 1;
 
     /* Now, possibly we can conseal chunks together */
     while ( order < FREELIST_SIZE )
@@ -320,9 +305,6 @@ void free_pages(void *pointer, int order)
             if ( allocated_in_map(virt_to_pfn(to_merge_ch)) ||
                  to_merge_ch->level != order )
                 break;
-
-            /* Merge with successor */
-            freed_ct = (chunk_tail_t *)((char *)to_merge_ch + mask) - 1;
         }
 
         /* We are committed to merging, unlink the chunk */
@@ -336,8 +318,6 @@ void free_pages(void *pointer, int order)
     freed_ch->level = order;
     freed_ch->next  = free_head[order];
     freed_ch->pprev = &free_head[order];
-    freed_ct->level = order;
-
     freed_ch->next->pprev = &freed_ch->next;
     free_head[order] = freed_ch;
 
Signature · 1 line
2.43.0
Reviewed-by on v1 2/4
#4 lore raw

Re: [PATCH 2/4] mini-os: mm: remove not needed struct chunk_tail_st

Juergen Gross, le lun. 22 juil. 2024 17:01:39 +0200, a ecrit:

Quoted 5 lines

The struct chunk_tail_st isn't really used other than writing to it.

Remove it in order to simplify the code.

Quoted 112 lines
---
 mm.c | 20 --------------------
 1 file changed, 20 deletions(-)
mm.c +0 -20
index 1dcd954c..2cc49e94 100644
@@ -123,7 +123,6 @@ static void map_free(unsigned long first_page, unsigned long nr_pages)
 /* BINARY BUDDY ALLOCATOR */
 
 typedef struct chunk_head_st chunk_head_t;
-typedef struct chunk_tail_st chunk_tail_t;
 
 struct chunk_head_st {
     chunk_head_t  *next;
@@ -131,10 +130,6 @@ struct chunk_head_st {
     int            level;
 };
 
-struct chunk_tail_st {
-    int level;
-};
-
 /* Linked lists of free chunks of different powers-of-two in size. */
 #define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT)
 static chunk_head_t *free_head[FREELIST_SIZE];
@@ -151,7 +146,6 @@ static void init_page_allocator(unsigned long min, unsigned long max)
     unsigned long range;
     unsigned long r_min, r_max;
     chunk_head_t *ch;
-    chunk_tail_t *ct;
 
     printk("MM: Initialise page allocator for %lx(%lx)-%lx(%lx)\n",
            (u_long)to_virt(min), min, (u_long)to_virt(max), max);
@@ -215,14 +209,12 @@ static void init_page_allocator(unsigned long min, unsigned long max)
             ch = (chunk_head_t *)r_min;
             r_min += 1UL << i;
             range -= 1UL << i;
-            ct = (chunk_tail_t *)r_min - 1;
             i -= PAGE_SHIFT;
             ch->level       = i;
             ch->next        = free_head[i];
             ch->pprev       = &free_head[i];
             ch->next->pprev = &ch->next;
             free_head[i]    = ch;
-            ct->level       = i;
         }
     }
 
@@ -234,7 +226,6 @@ unsigned long alloc_pages(int order)
 {
     int i;
     chunk_head_t *alloc_ch, *spare_ch;
-    chunk_tail_t            *spare_ct;
 
     if ( !chk_free_pages(1UL << order) )
         goto no_memory;
@@ -261,14 +252,11 @@ unsigned long alloc_pages(int order)
         i--;
         spare_ch = (chunk_head_t *)((char *)alloc_ch +
                                     (1UL << (i + PAGE_SHIFT)));
-        spare_ct = (chunk_tail_t *)((char *)spare_ch +
-                                    (1UL << (i + PAGE_SHIFT))) - 1;
 
         /* Create new header for spare chunk. */
         spare_ch->level = i;
         spare_ch->next  = free_head[i];
         spare_ch->pprev = &free_head[i];
-        spare_ct->level = i;
 
         /* Link in the spare chunk. */
         spare_ch->next->pprev = &spare_ch->next;
@@ -289,7 +277,6 @@ EXPORT_SYMBOL(alloc_pages);
 void free_pages(void *pointer, int order)
 {
     chunk_head_t *freed_ch, *to_merge_ch;
-    chunk_tail_t *freed_ct;
     unsigned long mask;
 
     /* First free the chunk */
@@ -297,8 +284,6 @@ void free_pages(void *pointer, int order)
 
     /* Create free chunk */
     freed_ch = (chunk_head_t *)pointer;
-    freed_ct = (chunk_tail_t *)((char *)pointer +
-                                (1UL << (order + PAGE_SHIFT))) - 1;
 
     /* Now, possibly we can conseal chunks together */
     while ( order < FREELIST_SIZE )
@@ -320,9 +305,6 @@ void free_pages(void *pointer, int order)
             if ( allocated_in_map(virt_to_pfn(to_merge_ch)) ||
                  to_merge_ch->level != order )
                 break;
-
-            /* Merge with successor */
-            freed_ct = (chunk_tail_t *)((char *)to_merge_ch + mask) - 1;
         }
 
         /* We are committed to merging, unlink the chunk */
@@ -336,8 +318,6 @@ void free_pages(void *pointer, int order)
     freed_ch->level = order;
     freed_ch->next  = free_head[order];
     freed_ch->pprev = &free_head[order];
-    freed_ct->level = order;
-
     freed_ch->next->pprev = &freed_ch->next;
     free_head[order] = freed_ch;
 
Signature · 1 line
2.43.0
Signature · 9 lines
Samuel
/*
 * [...] Note that 120 sec is defined in the protocol as the maximum
 * possible RTT.  I guess we'll have to use something other than TCP
 * to talk to the University of Mars.
 * PAWS allows us longer timeouts and large windows, so once implemented
 * ftp to mars will work nicely.
 */
(from /usr/src/linux/net/inet/tcp.c, concerning RTT [retransmission timeout])
#5 lore raw

PATCH 3/4 mini-os: mm: reduce buddy allocator list administration data

In reply to Juergen Gross

Today the administration data for the buddy allocator's lists consists of 2 arrays: one pointer array and one list element array for easier handling of the lists' tails.

Those arrays can be combined into one by dropping the pointer array and using a different list end indicator.

Add enqueue and dequeue helpers for better readability.

Change the level member type to unsigned int.

---
 mm.c | 73 ++++++++++++++++++++++++++++--------------------------------
 1 file changed, 34 insertions(+), 39 deletions(-)
mm.c +34 -39
index 2cc49e94..96686a5c 100644
@@ -125,16 +125,30 @@ static void map_free(unsigned long first_page, unsigned long nr_pages)
 typedef struct chunk_head_st chunk_head_t;
 
 struct chunk_head_st {
-    chunk_head_t  *next;
-    chunk_head_t **pprev;
-    int            level;
+    chunk_head_t *next;
+    chunk_head_t *prev;
+    unsigned int  level;
 };
 
 /* Linked lists of free chunks of different powers-of-two in size. */
 #define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT)
-static chunk_head_t *free_head[FREELIST_SIZE];
-static chunk_head_t  free_tail[FREELIST_SIZE];
-#define FREELIST_EMPTY(_l) ((_l)->next == NULL)
+static chunk_head_t  free_list[FREELIST_SIZE];
+#define FREELIST_EMPTY(_l) ((_l)->level == FREELIST_SIZE)
+
+static void enqueue_elem(chunk_head_t *elem, unsigned int level)
+{
+    elem->level = level;
+    elem->next = free_list[level].next;
+    elem->prev = &free_list[level];
+    elem->next->prev = elem;
+    free_list[level].next = elem;
+}
+
+static void dequeue_elem(chunk_head_t *elem)
+{
+    elem->prev->next = elem->next;
+    elem->next->prev = elem->prev;
+}
 
 /*
  * Initialise allocator, placing addresses [@min,@max] in free pool.
@@ -151,9 +165,9 @@ static void init_page_allocator(unsigned long min, unsigned long max)
            (u_long)to_virt(min), min, (u_long)to_virt(max), max);
     for ( i = 0; i < FREELIST_SIZE; i++ )
     {
-        free_head[i]       = &free_tail[i];
-        free_tail[i].pprev = &free_head[i];
-        free_tail[i].next  = NULL;
+        free_list[i].next  = &free_list[i];
+        free_list[i].prev  = &free_list[i];
+        free_list[i].level = FREELIST_SIZE;
     }
 
     min = round_pgup(min);
@@ -209,12 +223,7 @@ static void init_page_allocator(unsigned long min, unsigned long max)
             ch = (chunk_head_t *)r_min;
             r_min += 1UL << i;
             range -= 1UL << i;
-            i -= PAGE_SHIFT;
-            ch->level       = i;
-            ch->next        = free_head[i];
-            ch->pprev       = &free_head[i];
-            ch->next->pprev = &ch->next;
-            free_head[i]    = ch;
+            enqueue_elem(ch, i - PAGE_SHIFT);
         }
     }
 
@@ -233,17 +242,16 @@ unsigned long alloc_pages(int order)
     /* Find smallest order which can satisfy the request. */
     for ( i = order; i < FREELIST_SIZE; i++ )
     {
-        if ( !FREELIST_EMPTY(free_head[i]) )
+        if ( !FREELIST_EMPTY(free_list[i].next) )
             break;
     }
 
-    if ( i == FREELIST_SIZE )
+    if ( i >= FREELIST_SIZE )
         goto no_memory;
 
     /* Unlink a chunk. */
-    alloc_ch = free_head[i];
-    free_head[i] = alloc_ch->next;
-    alloc_ch->next->pprev = alloc_ch->pprev;
+    alloc_ch = free_list[i].next;
+    dequeue_elem(alloc_ch);
 
     /* We may have to break the chunk a number of times. */
     while ( i != order )
@@ -254,13 +262,7 @@ unsigned long alloc_pages(int order)
                                     (1UL << (i + PAGE_SHIFT)));
 
         /* Create new header for spare chunk. */
-        spare_ch->level = i;
-        spare_ch->next  = free_head[i];
-        spare_ch->pprev = &free_head[i];
-
-        /* Link in the spare chunk. */
-        spare_ch->next->pprev = &spare_ch->next;
-        free_head[i] = spare_ch;
+        enqueue_elem(spare_ch, i);
     }
 
     map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1UL << order);
@@ -308,18 +310,13 @@ void free_pages(void *pointer, int order)
         }
 
         /* We are committed to merging, unlink the chunk */
-        *(to_merge_ch->pprev) = to_merge_ch->next;
-        to_merge_ch->next->pprev = to_merge_ch->pprev;
+        dequeue_elem(to_merge_ch);
 
         order++;
     }
 
     /* Link the new chunk */
-    freed_ch->level = order;
-    freed_ch->next  = free_head[order];
-    freed_ch->pprev = &free_head[order];
-    freed_ch->next->pprev = &freed_ch->next;
-    free_head[order] = freed_ch;
+    enqueue_elem(freed_ch, order);
 
 }
 EXPORT_SYMBOL(free_pages);
@@ -405,13 +402,11 @@ void sanity_check(void)
 
     for ( x = 0; x < FREELIST_SIZE; x++ )
     {
-        for ( head = free_head[x]; !FREELIST_EMPTY(head); head = head->next )
+        for ( head = free_list[x].next; !FREELIST_EMPTY(head);
+              head = head->next )
         {
             ASSERT(!allocated_in_map(virt_to_pfn(head)));
-            if ( head->next )
-                ASSERT(head->next->pprev == &head->next);
+            ASSERT(head->next->prev == head);
         }
-        if ( free_head[x] )
-            ASSERT(free_head[x]->pprev == &free_head[x]);
     }
 }
Signature · 1 line
2.43.0
Reviewed-by on v1 3/4
#6 lore raw

Re: [PATCH 3/4] mini-os: mm: reduce buddy allocator list administration data

Juergen Gross, le lun. 22 juil. 2024 17:01:40 +0200, a ecrit:

Quoted 4 lines

Today the administration data for the buddy allocator's lists consists of 2 arrays: one pointer array and one list element array for easier handling of the lists' tails.

Quoted 8 lines

Those arrays can be combined into one by dropping the pointer array and using a different list end indicator.

Add enqueue and dequeue helpers for better readability.

Change the level member type to unsigned int.

Quoted 150 lines
---
 mm.c | 73 ++++++++++++++++++++++++++++--------------------------------
 1 file changed, 34 insertions(+), 39 deletions(-)
mm.c +34 -39
index 2cc49e94..96686a5c 100644
@@ -125,16 +125,30 @@ static void map_free(unsigned long first_page, unsigned long nr_pages)
 typedef struct chunk_head_st chunk_head_t;
 
 struct chunk_head_st {
-    chunk_head_t  *next;
-    chunk_head_t **pprev;
-    int            level;
+    chunk_head_t *next;
+    chunk_head_t *prev;
+    unsigned int  level;
 };
 
 /* Linked lists of free chunks of different powers-of-two in size. */
 #define FREELIST_SIZE ((sizeof(void *) << 3) - PAGE_SHIFT)
-static chunk_head_t *free_head[FREELIST_SIZE];
-static chunk_head_t  free_tail[FREELIST_SIZE];
-#define FREELIST_EMPTY(_l) ((_l)->next == NULL)
+static chunk_head_t  free_list[FREELIST_SIZE];
+#define FREELIST_EMPTY(_l) ((_l)->level == FREELIST_SIZE)
+
+static void enqueue_elem(chunk_head_t *elem, unsigned int level)
+{
+    elem->level = level;
+    elem->next = free_list[level].next;
+    elem->prev = &free_list[level];
+    elem->next->prev = elem;
+    free_list[level].next = elem;
+}
+
+static void dequeue_elem(chunk_head_t *elem)
+{
+    elem->prev->next = elem->next;
+    elem->next->prev = elem->prev;
+}
 
 /*
  * Initialise allocator, placing addresses [@min,@max] in free pool.
@@ -151,9 +165,9 @@ static void init_page_allocator(unsigned long min, unsigned long max)
            (u_long)to_virt(min), min, (u_long)to_virt(max), max);
     for ( i = 0; i < FREELIST_SIZE; i++ )
     {
-        free_head[i]       = &free_tail[i];
-        free_tail[i].pprev = &free_head[i];
-        free_tail[i].next  = NULL;
+        free_list[i].next  = &free_list[i];
+        free_list[i].prev  = &free_list[i];
+        free_list[i].level = FREELIST_SIZE;
     }
 
     min = round_pgup(min);
@@ -209,12 +223,7 @@ static void init_page_allocator(unsigned long min, unsigned long max)
             ch = (chunk_head_t *)r_min;
             r_min += 1UL << i;
             range -= 1UL << i;
-            i -= PAGE_SHIFT;
-            ch->level       = i;
-            ch->next        = free_head[i];
-            ch->pprev       = &free_head[i];
-            ch->next->pprev = &ch->next;
-            free_head[i]    = ch;
+            enqueue_elem(ch, i - PAGE_SHIFT);
         }
     }
 
@@ -233,17 +242,16 @@ unsigned long alloc_pages(int order)
     /* Find smallest order which can satisfy the request. */
     for ( i = order; i < FREELIST_SIZE; i++ )
     {
-        if ( !FREELIST_EMPTY(free_head[i]) )
+        if ( !FREELIST_EMPTY(free_list[i].next) )
             break;
     }
 
-    if ( i == FREELIST_SIZE )
+    if ( i >= FREELIST_SIZE )
         goto no_memory;
 
     /* Unlink a chunk. */
-    alloc_ch = free_head[i];
-    free_head[i] = alloc_ch->next;
-    alloc_ch->next->pprev = alloc_ch->pprev;
+    alloc_ch = free_list[i].next;
+    dequeue_elem(alloc_ch);
 
     /* We may have to break the chunk a number of times. */
     while ( i != order )
@@ -254,13 +262,7 @@ unsigned long alloc_pages(int order)
                                     (1UL << (i + PAGE_SHIFT)));
 
         /* Create new header for spare chunk. */
-        spare_ch->level = i;
-        spare_ch->next  = free_head[i];
-        spare_ch->pprev = &free_head[i];
-
-        /* Link in the spare chunk. */
-        spare_ch->next->pprev = &spare_ch->next;
-        free_head[i] = spare_ch;
+        enqueue_elem(spare_ch, i);
     }
 
     map_alloc(PHYS_PFN(to_phys(alloc_ch)), 1UL << order);
@@ -308,18 +310,13 @@ void free_pages(void *pointer, int order)
         }
 
         /* We are committed to merging, unlink the chunk */
-        *(to_merge_ch->pprev) = to_merge_ch->next;
-        to_merge_ch->next->pprev = to_merge_ch->pprev;
+        dequeue_elem(to_merge_ch);
 
         order++;
     }
 
     /* Link the new chunk */
-    freed_ch->level = order;
-    freed_ch->next  = free_head[order];
-    freed_ch->pprev = &free_head[order];
-    freed_ch->next->pprev = &freed_ch->next;
-    free_head[order] = freed_ch;
+    enqueue_elem(freed_ch, order);
 
 }
 EXPORT_SYMBOL(free_pages);
@@ -405,13 +402,11 @@ void sanity_check(void)
 
     for ( x = 0; x < FREELIST_SIZE; x++ )
     {
-        for ( head = free_head[x]; !FREELIST_EMPTY(head); head = head->next )
+        for ( head = free_list[x].next; !FREELIST_EMPTY(head);
+              head = head->next )
         {
             ASSERT(!allocated_in_map(virt_to_pfn(head)));
-            if ( head->next )
-                ASSERT(head->next->pprev == &head->next);
+            ASSERT(head->next->prev == head);
         }
-        if ( free_head[x] )
-            ASSERT(free_head[x]->pprev == &free_head[x]);
     }
 }
Signature · 1 line
2.43.0
Signature · 9 lines
Samuel
/*
 * [...] Note that 120 sec is defined in the protocol as the maximum
 * possible RTT.  I guess we'll have to use something other than TCP
 * to talk to the University of Mars.
 * PAWS allows us longer timeouts and large windows, so once implemented
 * ftp to mars will work nicely.
 */
(from /usr/src/linux/net/inet/tcp.c, concerning RTT [retransmission timeout])
#7 lore raw

PATCH 4/4 mini-os: remove sanity_check()

In reply to Juergen Gross

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

---
 include/lib.h |  3 ---
 mm.c          | 16 ----------------
 2 files changed, 19 deletions(-)
include/lib.h +0 -3
index abd4e9ab..acd4acc6 100644
@@ -152,9 +152,6 @@ do {                                                           \
 
 #define BUG_ON(x) ASSERT(!(x))
 
-/* Consistency check as much as possible. */
-void sanity_check(void);
-
 /* Get own domid. */
 domid_t get_domid(void);
 
mm.c +0 -16
index 96686a5c..1fa7e7bf 100644
@@ -394,19 +394,3 @@ void init_mm(void)
 void fini_mm(void)
 {
 }
-
-void sanity_check(void)
-{
-    int x;
-    chunk_head_t *head;
-
-    for ( x = 0; x < FREELIST_SIZE; x++ )
-    {
-        for ( head = free_list[x].next; !FREELIST_EMPTY(head);
-              head = head->next )
-        {
-            ASSERT(!allocated_in_map(virt_to_pfn(head)));
-            ASSERT(head->next->prev == head);
-        }
-    }
-}
Signature · 1 line
2.43.0
#8 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Samuel

Quoted 47 lines
---
 include/lib.h |  3 ---
 mm.c          | 16 ----------------
 2 files changed, 19 deletions(-)
include/lib.h +0 -3
index abd4e9ab..acd4acc6 100644
@@ -152,9 +152,6 @@ do {                                                           \
 
 #define BUG_ON(x) ASSERT(!(x))
 
-/* Consistency check as much as possible. */
-void sanity_check(void);
-
 /* Get own domid. */
 domid_t get_domid(void);
 
mm.c +0 -16
index 96686a5c..1fa7e7bf 100644
@@ -394,19 +394,3 @@ void init_mm(void)
 void fini_mm(void)
 {
 }
-
-void sanity_check(void)
-{
-    int x;
-    chunk_head_t *head;
-
-    for ( x = 0; x < FREELIST_SIZE; x++ )
-    {
-        for ( head = free_list[x].next; !FREELIST_EMPTY(head);
-              head = head->next )
-        {
-            ASSERT(!allocated_in_map(virt_to_pfn(head)));
-            ASSERT(head->next->prev == head);
-        }
-    }
-}
Signature · 1 line
2.43.0
Signature · 9 lines
Samuel
/*
 * [...] Note that 120 sec is defined in the protocol as the maximum
 * possible RTT.  I guess we'll have to use something other than TCP
 * to talk to the University of Mars.
 * PAWS allows us longer timeouts and large windows, so once implemented
 * ftp to mars will work nicely.
 */
(from /usr/src/linux/net/inet/tcp.c, concerning RTT [retransmission timeout])
#9 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Quoted 9 lines · Samuel Thibault

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Hmm, is it really worth the extra code?

There are 2 ASSERT()s I'm deleting: one testing the allocation bitmap to match the comment further up:

/*
* ALLOCATION BITMAP
* One bit per page of memory. Bit set => page is allocated. */

And the other one testing the linked lists being correct, which IMO doesn't need any further documentation.

Juergen

#10 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Hello,

Jürgen Groß, le mar. 23 juil. 2024 08:36:13 +0200, a ecrit:

Quoted 12 lines · Samuel Thibault
Quoted 9 lines

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Hmm, is it really worth the extra code?

I have already seen such kind of piece of code getting very convenient when tracking odd bugs.

Samuel

#11 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Quoted 11 lines · Samuel Thibault

Hello,

Jürgen Groß, le mar. 23 juil. 2024 08:36:13 +0200, a ecrit:

Quoted 8 lines · Samuel Thibault
Quoted 7 lines

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Hmm, is it really worth the extra code?

I have already seen such kind of piece of code getting very convenient when tracking odd bugs.

What about putting it under CONFIG_TEST then?

This would keep it in the source and it would even be compile tested by a simple "make testbuild", which is a simple test I'm always doing before submitting a patch.

Juergen

#12 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Jürgen Groß, le jeu. 25 juil. 2024 08:25:18 +0200, a ecrit:

Quoted 15 lines · Samuel Thibault
Quoted 14 lines

Hello,

Jürgen Groß, le mar. 23 juil. 2024 08:36:13 +0200, a ecrit:

Quoted 11 lines · Samuel Thibault
Quoted 9 lines

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

Hmm, is it really worth the extra code?

I have already seen such kind of piece of code getting very convenient when tracking odd bugs.

What about putting it under CONFIG_TEST then?

Ok !

Samuel

#13 lore raw

Re: [PATCH 4/4] mini-os: remove sanity_check()

Quoted 16 lines · Samuel Thibault

Jürgen Groß, le jeu. 25 juil. 2024 08:25:18 +0200, a ecrit:

Quoted 15 lines · Samuel Thibault
Quoted 14 lines

Hello,

Jürgen Groß, le mar. 23 juil. 2024 08:36:13 +0200, a ecrit:

Quoted 11 lines · Samuel Thibault
Quoted 9 lines

Juergen Gross, le lun. 22 juil. 2024 17:01:41 +0200, a ecrit:

Quoted 5 lines

Remove the sanity_check() function, as it is used nowhere.

Since any application linked with Mini-OS can't call sanity_check() either (there is no EXPORT_SYMBOL for it), there is zero chance of breaking any use case.

Don't we still want to keep it around, at least as formal documentation of the expected status of the list?

Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
Quoted 1 line

Hmm, is it really worth the extra code?

I have already seen such kind of piece of code getting very convenient when tracking odd bugs.

What about putting it under CONFIG_TEST then?

Ok !

I went a little bit further by calling sanity_check() from periodic_thread() in test.c once a second. This will make real use of the function.

Juergen