mini-os: cleanup of mm.c
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
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
@@ -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
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
PATCH 2/4 mini-os: mm: remove not needed struct chunk_tail_st
In reply to Juergen GrossThe 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
@@ -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
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_stisn't really used other than writing to it.Remove it in order to simplify the code.
Signed-off-by Juergen Gross <[email protected]>
Quoted 112 lines
--- mm.c | 20 -------------------- 1 file changed, 20 deletions(-)mm.c +0
-20@@ -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])
PATCH 3/4 mini-os: mm: reduce buddy allocator list administration data
In reply to Juergen GrossToday 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
@@ -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
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.
Signed-off-by Juergen Gross <[email protected]>
Quoted 150 lines
--- mm.c | 73 ++++++++++++++++++++++++++++-------------------------------- 1 file changed, 34 insertions(+), 39 deletions(-)mm.c +34
-39@@ -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])
PATCH 4/4 mini-os: remove sanity_check()
In reply to Juergen GrossRemove 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
@@ -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
@@ -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
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 noEXPORT_SYMBOLfor 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
Signed-off-by Juergen Gross <[email protected]>--- include/lib.h | 3 --- mm.c | 16 ---------------- 2 files changed, 19 deletions(-)include/lib.h +0
-3@@ -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@@ -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])
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 noEXPORT_SYMBOLfor 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
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 noEXPORT_SYMBOLfor 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
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 noEXPORT_SYMBOLfor 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
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 noEXPORT_SYMBOLfor 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_TESTthen?
Ok !
Samuel
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 noEXPORT_SYMBOLfor 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_TESTthen?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