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