1#pragma once
2#include <compiler/core.h>
3#include <math/bit.h>
4#include <math/min_max.h>
5#include <mem/bitmap.h>
6#include <mem/buddy.h>
7#include <mem/page.h>
8#include <stdbool.h>
9#include <stdint.h>
10#include <sync/spinlock.h>
11#include <types/types.h>
12
13#define PAGE_TO_BUDDY_PAGE(p) ((struct buddy_page *) (p))
14#define BUDDY_PAGE_TO_PAGE(p) ((struct page *) (p))
15
16/*
17 * Layout of buddy_page::meta
18 * bits [0, 2] : page tag (PAGE_TAG_*)
19 * bit [3] : is_free
20 * bit [4] : is_zeroed
21 * bits [5, 11] : order (7 bits)
22 * bits [12, 63] : next_pfn (52 bits)
23 */
24#define BUDDY_IS_FREE_SHIFT 3
25#define BUDDY_IS_FREE_MASK BIT(BUDDY_IS_FREE_SHIFT)
26
27#define BUDDY_IS_ZEROED_SHIFT 4
28#define BUDDY_IS_ZEROED_MASK BIT(BUDDY_IS_ZEROED_SHIFT)
29
30#define BUDDY_ORDER_SHIFT 5
31#define BUDDY_ORDER_BITS 7
32#define BUDDY_ORDER_MASK ((BIT(BUDDY_ORDER_BITS) - 1) << BUDDY_ORDER_SHIFT)
33
34#define BUDDY_NEXT_PFN_SHIFT PAGE_4K_SHIFT
35#define BUDDY_NEXT_PFN_BITS (64 - PAGE_4K_SHIFT)
36#define BUDDY_NEXT_PFN_MASK \
37 ((BIT(BUDDY_NEXT_PFN_BITS) - 1) << BUDDY_NEXT_PFN_SHIFT)
38
39struct buddy_page {
40 uint64_t meta;
41};
42ct_assert_struct_size_eq(buddy_page, 8);
43
44static inline uint64_t buddy_page_get_order(const struct buddy_page *bp) {
45 return (bp->meta & BUDDY_ORDER_MASK) >> BUDDY_ORDER_SHIFT;
46}
47
48static inline void buddy_page_set_order(struct buddy_page *bp, uint64_t order) {
49 bp->meta = (bp->meta & ~BUDDY_ORDER_MASK) |
50 ((order << BUDDY_ORDER_SHIFT) & BUDDY_ORDER_MASK);
51}
52
53static inline pfn_t buddy_page_get_next_pfn(const struct buddy_page *bp) {
54 return (pfn_t) ((bp->meta & BUDDY_NEXT_PFN_MASK) >> BUDDY_NEXT_PFN_SHIFT);
55}
56
57static inline void buddy_page_set_next_pfn(struct buddy_page *bp, pfn_t pfn) {
58 bp->meta = (bp->meta & ~BUDDY_NEXT_PFN_MASK) |
59 (((uint64_t) pfn << BUDDY_NEXT_PFN_SHIFT) & BUDDY_NEXT_PFN_MASK);
60}
61
62static inline bool buddy_page_is_free(const struct buddy_page *bp) {
63 return page_get_tag(p: (const struct page *) bp) == PAGE_TAG_BUDDY &&
64 (bp->meta & BUDDY_IS_FREE_MASK) != 0;
65}
66
67static inline void buddy_page_set_free(struct buddy_page *bp, bool is_free) {
68 bp->meta =
69 (bp->meta & ~BUDDY_IS_FREE_MASK) | (is_free ? BUDDY_IS_FREE_MASK : 0);
70}
71
72static inline bool buddy_page_is_zeroed(const struct buddy_page *bp) {
73 return (bp->meta & BUDDY_IS_ZEROED_MASK) != 0;
74}
75
76static inline void buddy_page_set_zeroed(struct buddy_page *bp,
77 bool is_zeroed) {
78 bp->meta = (bp->meta & ~BUDDY_IS_ZEROED_MASK) |
79 (is_zeroed ? BUDDY_IS_ZEROED_MASK : 0);
80}
81
82static inline bool page_pfn_allocated_in_boot_bitmap(pfn_t pfn) {
83 return test_bit(index: pfn);
84}
85
86static inline bool buddy_page_pfn_free(pfn_t pfn) {
87 if (pfn >= global.last_pfn)
88 return false;
89
90 struct page *p = &global.page_array[pfn];
91
92 return buddy_page_is_free(bp: (struct buddy_page *) p);
93}
94
95static inline struct buddy_page *buddy_page_for_pfn(pfn_t pfn) {
96 return PAGE_TO_BUDDY_PAGE(page_for_pfn(pfn));
97}
98
99static inline pfn_t buddy_page_get_pfn(struct buddy_page *bp) {
100 return page_get_pfn(bp: (struct page *) bp);
101}
102
103static inline paddr_t buddy_page_get_paddr(struct buddy_page *bp) {
104 return PFN_TO_PAGE(buddy_page_get_pfn(bp));
105}
106
107static inline void buddy_page_set_next(struct buddy_page *bp,
108 struct buddy_page *next) {
109 if (!next)
110 return buddy_page_set_next_pfn(bp, pfn: 0);
111
112 buddy_page_set_next_pfn(bp, pfn: buddy_page_get_pfn(bp: next));
113}
114
115static inline struct buddy_page *buddy_page_get_next(struct buddy_page *bp) {
116 pfn_t pfn = buddy_page_get_next_pfn(bp);
117 if (pfn == 0)
118 return NULL;
119
120 return buddy_page_for_pfn(pfn);
121}
122
123struct buddy_free_link {
124 struct buddy_page *prev;
125};
126
127static inline struct buddy_free_link *
128buddy_page_free_link(struct buddy_page *bp) {
129 return (struct buddy_free_link *) hhdm_paddr_to_ptr(
130 p: buddy_page_get_paddr(bp));
131}
132
133static inline struct buddy_page *buddy_page_get_prev(struct buddy_page *bp) {
134 return buddy_page_free_link(bp)->prev;
135}
136
137static inline void buddy_page_set_prev(struct buddy_page *bp,
138 struct buddy_page *prev) {
139 buddy_page_free_link(bp)->prev = prev;
140}
141
142static inline void buddy_page_tag(struct buddy_page *page) {
143 if (page)
144 page_set_tag(BUDDY_PAGE_TO_PAGE(page), tag: PAGE_TAG_BUDDY);
145}
146
147static inline void buddy_page_untag(struct buddy_page *page) {
148 if (page)
149 page_set_tag(BUDDY_PAGE_TO_PAGE(page), tag: PAGE_TAG_NONE);
150}
151
152static inline void buddy_page_assert_tag(struct buddy_page *page,
153 enum page_tag tag) {
154 if (page)
155 page_assert_tag(BUDDY_PAGE_TO_PAGE(page), expected: tag);
156}
157
158bool buddy_fa_empty(struct buddy_free_area *area);
159struct buddy_page *buddy_fa_get_head(struct buddy_free_area *area);
160struct buddy_page *buddy_fa_get_tail(struct buddy_free_area *area);
161void buddy_fa_push_head(struct buddy_free_area *area, struct buddy_page *page);
162void buddy_fa_push_tail(struct buddy_free_area *area, struct buddy_page *page);
163struct buddy_page *buddy_fa_pop_head(struct buddy_free_area *area);
164struct buddy_page *buddy_fa_pop_tail(struct buddy_free_area *area);
165void buddy_fa_remove(struct buddy_free_area *area, struct buddy_page *page);
166