I spent a while talking to Doug about it and asking him why he added
new free blocks to the end of the free lists, so they were used in FIFO
order. Wouldn't LIFO give better cache results?
The answer might be applicable to the Linux kernel page allocator.
Using LIFO order increases fragmentation *drastically*, to the point
where the larger size of the arena has bad cache effects.
Letting each free block sit on a free list for a while gives it time to
combine with other frees to make a larger block. Blocks that get combined
go back onto the end of the new free list to be combined further.
Blocks whose neighbours don't get freed make it to the front of the free
list and get reused for their original size.
When you use blocks in LIFO (stack) order, the back of the list gets clogged
up with blocks that don't get used and don't get combined, either. Because
no neighbours want to combine with them, allocating them doesn't block any
defragmentation, so they're the best blocks to put to use. But instead
a few blocks at the head of the list get all the traffic.
I don't really follow the free page code, but as far as I can tell,
this small patch should do the right thing. Could someone who has the
memory code instrumented tell me if this makes any difference?
-- -Colin--- linux/mm/page_alloc.c Mon Jun 1 04:31:48 1998 +++ linux/mm/page_alloc.c Thu Jul 16 02:08:55 1998 @@ -65,12 +65,12 @@ static inline void add_mem_queue(struct free_area_struct * head, struct page * entry) { - struct page * next = head->next; + struct page * prev = head->prev; - entry->prev = memory_head(head); - entry->next = next; - next->prev = entry; - head->next = entry; + entry->next = memory_head(head); + entry->prev = prev; + prev->next = entry; + head->prev = entry; } static inline void remove_mem_queue(struct page * entry)
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html