1 /* $OpenBSD: subr_hibernate.c,v 1.1 2011/07/08 17:58:16 ariane Exp $ */ 2 3 /* 4 * Copyright (c) 2011 Ariane van der Steldt <ariane@stack.nl> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <sys/hibernate.h> 20 #include <sys/param.h> 21 #include <sys/tree.h> 22 #include <sys/types.h> 23 #include <sys/systm.h> 24 25 26 /* 27 * Hib alloc enforced alignment. 28 */ 29 #define HIB_ALIGN 8 /* bytes alignment */ 30 31 /* 32 * sizeof builtin operation, but with alignment constraint. 33 */ 34 #define HIB_SIZEOF(_type) roundup(sizeof(_type), HIB_ALIGN) 35 36 struct hiballoc_entry 37 { 38 size_t hibe_use; 39 size_t hibe_space; 40 RB_ENTRY(hiballoc_entry) hibe_entry; 41 }; 42 43 /* 44 * Compare hiballoc entries based on the address they manage. 45 * 46 * Since the address is fixed, relative to struct hiballoc_entry, 47 * we just compare the hiballoc_entry pointers. 48 */ 49 static __inline int 50 hibe_cmp(struct hiballoc_entry *l, struct hiballoc_entry *r) 51 { 52 return l < r ? -1 : (l > r); 53 } 54 55 RB_PROTOTYPE(hiballoc_addr, hiballoc_entry, hibe_entry, hibe_cmp) 56 57 /* 58 * Given a hiballoc entry, return the address it manages. 59 */ 60 static __inline void* 61 hib_entry_to_addr(struct hiballoc_entry *entry) 62 { 63 caddr_t addr; 64 65 addr = (caddr_t)entry; 66 addr += HIB_SIZEOF(struct hiballoc_entry); 67 return addr; 68 } 69 70 /* 71 * Given an address, find the hiballoc that corresponds. 72 */ 73 static __inline struct hiballoc_entry* 74 hib_addr_to_entry(void* addr_param) 75 { 76 caddr_t addr; 77 78 addr = (caddr_t)addr_param; 79 addr -= HIB_SIZEOF(struct hiballoc_entry); 80 return (struct hiballoc_entry*)addr; 81 } 82 83 RB_GENERATE(hiballoc_addr, hiballoc_entry, hibe_entry, hibe_cmp) 84 85 /* 86 * Allocate memory from the arena. 87 * 88 * Returns NULL if no memory is available. 89 */ 90 void* 91 hib_alloc(struct hiballoc_arena *arena, size_t alloc_sz) 92 { 93 struct hiballoc_entry *entry, *new_entry; 94 size_t find_sz; 95 96 /* 97 * Enforce alignment of HIB_ALIGN bytes. 98 * 99 * Note that, because the entry is put in front of the allocation, 100 * 0-byte allocations are guaranteed a unique address. 101 */ 102 alloc_sz = roundup(alloc_sz, HIB_ALIGN); 103 104 /* 105 * Find an entry with hibe_space >= find_sz. 106 * 107 * If the root node is not large enough, we switch to tree traversal. 108 * Because all entries are made at the bottom of the free space, 109 * traversal from the end has a slightly better chance of yielding 110 * a sufficiently large space. 111 */ 112 find_sz = alloc_sz + HIB_SIZEOF(struct hiballoc_entry); 113 entry = RB_ROOT(&arena->hib_addrs); 114 if (entry != NULL && entry->hibe_space < find_sz) { 115 RB_FOREACH_REVERSE(entry, hiballoc_addr, &arena->hib_addrs) { 116 if (entry->hibe_space >= find_sz) 117 break; 118 } 119 } 120 121 /* 122 * Insufficient or too fragmented memory. 123 */ 124 if (entry == NULL) 125 return NULL; 126 127 /* 128 * Create new entry in allocated space. 129 */ 130 new_entry = (struct hiballoc_entry*)( 131 (caddr_t)hib_entry_to_addr(entry) + entry->hibe_use); 132 new_entry->hibe_space = entry->hibe_space - find_sz; 133 new_entry->hibe_use = alloc_sz; 134 135 /* 136 * Insert entry. 137 */ 138 if (RB_INSERT(hiballoc_addr, &arena->hib_addrs, new_entry) != NULL) 139 panic("hib_alloc: insert failure"); 140 entry->hibe_space = 0; 141 142 /* Return address managed by entry. */ 143 return hib_entry_to_addr(new_entry); 144 } 145 146 /* 147 * Free a pointer previously allocated from this arena. 148 * 149 * If addr is NULL, this will be silently accepted. 150 */ 151 void 152 hib_free(struct hiballoc_arena *arena, void *addr) 153 { 154 struct hiballoc_entry *entry, *prev; 155 156 if (addr == NULL) 157 return; 158 159 /* 160 * Derive entry from addr and check it is really in this arena. 161 */ 162 entry = hib_addr_to_entry(addr); 163 if (RB_FIND(hiballoc_addr, &arena->hib_addrs, entry) != entry) 164 panic("hib_free: freed item %p not in hib arena", addr); 165 166 /* 167 * Give the space in entry to its predecessor. 168 * 169 * If entry has no predecessor, change its used space into free space 170 * instead. 171 */ 172 prev = RB_PREV(hiballoc_addr, &arena->hib_addrs, entry); 173 if (prev != NULL && 174 (void*)((caddr_t)prev + HIB_SIZEOF(struct hiballoc_entry) + 175 prev->hibe_use + prev->hibe_space) == entry) { 176 /* Merge entry. */ 177 RB_REMOVE(hiballoc_addr, &arena->hib_addrs, entry); 178 prev->hibe_space += HIB_SIZEOF(struct hiballoc_entry) + 179 entry->hibe_use + entry->hibe_space; 180 } else { 181 /* Flip used memory to free space. */ 182 entry->hibe_space += entry->hibe_use; 183 entry->hibe_use = 0; 184 } 185 } 186 187 /* 188 * Initialize hiballoc. 189 * 190 * The allocator will manage memmory at ptr, which is len bytes. 191 */ 192 int 193 hiballoc_init(struct hiballoc_arena *arena, void *p_ptr, size_t p_len) 194 { 195 struct hiballoc_entry *entry; 196 caddr_t ptr; 197 size_t len; 198 199 RB_INIT(&arena->hib_addrs); 200 201 /* 202 * Hib allocator enforces HIB_ALIGN alignment. 203 * Fixup ptr and len. 204 */ 205 ptr = (caddr_t)roundup((vaddr_t)p_ptr, HIB_ALIGN); 206 len = p_len - ((size_t)ptr - (size_t)p_ptr); 207 len &= ~((size_t)HIB_ALIGN - 1); 208 209 /* 210 * Insufficient memory to be able to allocate and also do bookkeeping. 211 */ 212 if (len <= HIB_SIZEOF(struct hiballoc_entry)) 213 return ENOMEM; 214 215 /* 216 * Create entry describing space. 217 */ 218 entry = (struct hiballoc_entry*)ptr; 219 entry->hibe_use = 0; 220 entry->hibe_space = len - HIB_SIZEOF(struct hiballoc_entry); 221 RB_INSERT(hiballoc_addr, &arena->hib_addrs, entry); 222 223 return 0; 224 } 225