jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#pragma once
8
9#include <AK/Bitmap.h>
10#include <AK/IntrusiveList.h>
11
12namespace Kernel::Memory {
13
14// A PhysicalZone is an allocator that manages a sub-area of a PhysicalRegion.
15// Its total size is always a power of two.
16// You allocate chunks at a time. One chunk is PAGE_SIZE/2, and the minimum allocation size is 2 chunks.
17// The allocator uses a buddy block scheme internally.
18
19class PhysicalZone {
20 AK_MAKE_NONCOPYABLE(PhysicalZone);
21 AK_MAKE_NONMOVABLE(PhysicalZone);
22
23public:
24 static constexpr size_t ZONE_CHUNK_SIZE = PAGE_SIZE / 2;
25 using ChunkIndex = i16;
26
27 PhysicalZone(PhysicalAddress base, size_t page_count);
28
29 Optional<PhysicalAddress> allocate_block(size_t order);
30 void deallocate_block(PhysicalAddress, size_t order);
31
32 void dump() const;
33 size_t available() const { return m_page_count - (m_used_chunks / 2); }
34
35 bool is_empty() const { return available() == 0; }
36
37 PhysicalAddress base() const { return m_base_address; }
38 bool contains(PhysicalAddress paddr) const
39 {
40 return paddr >= m_base_address && paddr < m_base_address.offset(m_page_count * PAGE_SIZE);
41 }
42
43private:
44 Optional<ChunkIndex> allocate_block_impl(size_t order);
45 void deallocate_block_impl(ChunkIndex, size_t order);
46
47 struct BuddyBucket {
48 bool get_buddy_bit(ChunkIndex index) const
49 {
50 return bitmap.get(buddy_bit_index(index));
51 }
52
53 void set_buddy_bit(ChunkIndex index, bool value)
54 {
55 bitmap.set(buddy_bit_index(index), value);
56 }
57
58 size_t buddy_bit_index(ChunkIndex index) const
59 {
60 // NOTE: We cut the index in half since one chunk is half a page.
61 return (index >> 1) >> (1 + order);
62 }
63
64 // This bucket's index in the m_buckets array. (Redundant data kept here for convenience.)
65 size_t order { 0 };
66
67 // This is the start of the freelist for this buddy size.
68 // It's an index into the global PhysicalPageEntry array (offset by this PhysicalRegion's base.)
69 // A value of -1 indicates an empty freelist.
70 ChunkIndex freelist { -1 };
71
72 // Bitmap with 1 bit per buddy pair.
73 // 0 == Both blocks either free or used.
74 // 1 == One block free, one block used.
75 Bitmap bitmap;
76 };
77
78 static constexpr size_t max_order = 12;
79 BuddyBucket m_buckets[max_order + 1];
80
81 PhysicalPageEntry& get_freelist_entry(ChunkIndex) const;
82 void remove_from_freelist(BuddyBucket&, ChunkIndex);
83
84 PhysicalAddress m_base_address { 0 };
85 size_t m_page_count { 0 };
86 size_t m_used_chunks { 0 };
87
88 IntrusiveListNode<PhysicalZone> m_list_node;
89
90public:
91 using List = IntrusiveList<&PhysicalZone::m_list_node>;
92};
93
94}