| Message ID | 20240722150141.31391-4-jgross@suse.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | mini-os: cleanup of mm.c | expand |
Juergen Gross, le lun. 22 juil. 2024 17:01:40 +0200, a ecrit: > 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. > > Signed-off-by: Juergen Gross <jgross@suse.com> Reviewed-by: Samuel Thibault <samuel.thibault@ens-lyon.org> > --- > mm.c | 73 ++++++++++++++++++++++++++++-------------------------------- > 1 file changed, 34 insertions(+), 39 deletions(-) > > diff --git a/mm.c b/mm.c > index 2cc49e94..96686a5c 100644 > --- a/mm.c > +++ b/mm.c > @@ -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]); > } > } > -- > 2.43.0 >
diff --git a/mm.c b/mm.c index 2cc49e94..96686a5c 100644 --- a/mm.c +++ b/mm.c @@ -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]); } }
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. Signed-off-by: Juergen Gross <jgross@suse.com> --- mm.c | 73 ++++++++++++++++++++++++++++-------------------------------- 1 file changed, 34 insertions(+), 39 deletions(-)