The workings of the page allocator

The actual (de)allocation strategy can be explained by using a simple example. Let's say a device driver requests 128 KB of memory. To fulfill this request, the (simplified and conceptual) page allocator algorithm will do this:

1. The algorithm expresses the amount to be allocated (128 KB here) in pages. Thus, here, it's (assuming a page size of 4 KB) 128/4 = 32 pages.
2. Next, it determines to what power 2 must be raised to get 32. That's log₂32, which is 5 (as 2⁵ is 32).
3. Now, it checks the list on order 5 of the appropriate node:zone page allocator freelist. If a memory chunk is available (it will be of size 2⁵ pages = 128 KB), dequeue it from the list, update the list, and allocate it to the requester. Job done! Return to caller.