1 /* $OpenBSD: subr_hibernate.c,v 1.3 2011/07/08 18:25:56 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 #include <uvm/uvm.h> 25 26 27 /* 28 * Hib alloc enforced alignment. 29 */ 30 #define HIB_ALIGN 8 /* bytes alignment */ 31 32 /* 33 * sizeof builtin operation, but with alignment constraint. 34 */ 35 #define HIB_SIZEOF(_type) roundup(sizeof(_type), HIB_ALIGN) 36 37 struct hiballoc_entry 38 { 39 size_t hibe_use; 40 size_t hibe_space; 41 RB_ENTRY(hiballoc_entry) hibe_entry; 42 }; 43 44 /* 45 * Compare hiballoc entries based on the address they manage. 46 * 47 * Since the address is fixed, relative to struct hiballoc_entry, 48 * we just compare the hiballoc_entry pointers. 49 */ 50 static __inline int 51 hibe_cmp(struct hiballoc_entry *l, struct hiballoc_entry *r) 52 { 53 return l < r ? -1 : (l > r); 54 } 55 56 RB_PROTOTYPE(hiballoc_addr, hiballoc_entry, hibe_entry, hibe_cmp) 57 58 /* 59 * Given a hiballoc entry, return the address it manages. 60 */ 61 static __inline void* 62 hib_entry_to_addr(struct hiballoc_entry *entry) 63 { 64 caddr_t addr; 65 66 addr = (caddr_t)entry; 67 addr += HIB_SIZEOF(struct hiballoc_entry); 68 return addr; 69 } 70 71 /* 72 * Given an address, find the hiballoc that corresponds. 73 */ 74 static __inline struct hiballoc_entry* 75 hib_addr_to_entry(void* addr_param) 76 { 77 caddr_t addr; 78 79 addr = (caddr_t)addr_param; 80 addr -= HIB_SIZEOF(struct hiballoc_entry); 81 return (struct hiballoc_entry*)addr; 82 } 83 84 RB_GENERATE(hiballoc_addr, hiballoc_entry, hibe_entry, hibe_cmp) 85 86 /* 87 * Allocate memory from the arena. 88 * 89 * Returns NULL if no memory is available. 90 */ 91 void* 92 hib_alloc(struct hiballoc_arena *arena, size_t alloc_sz) 93 { 94 struct hiballoc_entry *entry, *new_entry; 95 size_t find_sz; 96 97 /* 98 * Enforce alignment of HIB_ALIGN bytes. 99 * 100 * Note that, because the entry is put in front of the allocation, 101 * 0-byte allocations are guaranteed a unique address. 102 */ 103 alloc_sz = roundup(alloc_sz, HIB_ALIGN); 104 105 /* 106 * Find an entry with hibe_space >= find_sz. 107 * 108 * If the root node is not large enough, we switch to tree traversal. 109 * Because all entries are made at the bottom of the free space, 110 * traversal from the end has a slightly better chance of yielding 111 * a sufficiently large space. 112 */ 113 find_sz = alloc_sz + HIB_SIZEOF(struct hiballoc_entry); 114 entry = RB_ROOT(&arena->hib_addrs); 115 if (entry != NULL && entry->hibe_space < find_sz) { 116 RB_FOREACH_REVERSE(entry, hiballoc_addr, &arena->hib_addrs) { 117 if (entry->hibe_space >= find_sz) 118 break; 119 } 120 } 121 122 /* 123 * Insufficient or too fragmented memory. 124 */ 125 if (entry == NULL) 126 return NULL; 127 128 /* 129 * Create new entry in allocated space. 130 */ 131 new_entry = (struct hiballoc_entry*)( 132 (caddr_t)hib_entry_to_addr(entry) + entry->hibe_use); 133 new_entry->hibe_space = entry->hibe_space - find_sz; 134 new_entry->hibe_use = alloc_sz; 135 136 /* 137 * Insert entry. 138 */ 139 if (RB_INSERT(hiballoc_addr, &arena->hib_addrs, new_entry) != NULL) 140 panic("hib_alloc: insert failure"); 141 entry->hibe_space = 0; 142 143 /* Return address managed by entry. */ 144 return hib_entry_to_addr(new_entry); 145 } 146 147 /* 148 * Free a pointer previously allocated from this arena. 149 * 150 * If addr is NULL, this will be silently accepted. 151 */ 152 void 153 hib_free(struct hiballoc_arena *arena, void *addr) 154 { 155 struct hiballoc_entry *entry, *prev; 156 157 if (addr == NULL) 158 return; 159 160 /* 161 * Derive entry from addr and check it is really in this arena. 162 */ 163 entry = hib_addr_to_entry(addr); 164 if (RB_FIND(hiballoc_addr, &arena->hib_addrs, entry) != entry) 165 panic("hib_free: freed item %p not in hib arena", addr); 166 167 /* 168 * Give the space in entry to its predecessor. 169 * 170 * If entry has no predecessor, change its used space into free space 171 * instead. 172 */ 173 prev = RB_PREV(hiballoc_addr, &arena->hib_addrs, entry); 174 if (prev != NULL && 175 (void*)((caddr_t)prev + HIB_SIZEOF(struct hiballoc_entry) + 176 prev->hibe_use + prev->hibe_space) == entry) { 177 /* Merge entry. */ 178 RB_REMOVE(hiballoc_addr, &arena->hib_addrs, entry); 179 prev->hibe_space += HIB_SIZEOF(struct hiballoc_entry) + 180 entry->hibe_use + entry->hibe_space; 181 } else { 182 /* Flip used memory to free space. */ 183 entry->hibe_space += entry->hibe_use; 184 entry->hibe_use = 0; 185 } 186 } 187 188 /* 189 * Initialize hiballoc. 190 * 191 * The allocator will manage memmory at ptr, which is len bytes. 192 */ 193 int 194 hiballoc_init(struct hiballoc_arena *arena, void *p_ptr, size_t p_len) 195 { 196 struct hiballoc_entry *entry; 197 caddr_t ptr; 198 size_t len; 199 200 RB_INIT(&arena->hib_addrs); 201 202 /* 203 * Hib allocator enforces HIB_ALIGN alignment. 204 * Fixup ptr and len. 205 */ 206 ptr = (caddr_t)roundup((vaddr_t)p_ptr, HIB_ALIGN); 207 len = p_len - ((size_t)ptr - (size_t)p_ptr); 208 len &= ~((size_t)HIB_ALIGN - 1); 209 210 /* 211 * Insufficient memory to be able to allocate and also do bookkeeping. 212 */ 213 if (len <= HIB_SIZEOF(struct hiballoc_entry)) 214 return ENOMEM; 215 216 /* 217 * Create entry describing space. 218 */ 219 entry = (struct hiballoc_entry*)ptr; 220 entry->hibe_use = 0; 221 entry->hibe_space = len - HIB_SIZEOF(struct hiballoc_entry); 222 RB_INSERT(hiballoc_addr, &arena->hib_addrs, entry); 223 224 return 0; 225 } 226 227 228 /* 229 * Zero all free memory. 230 */ 231 void 232 uvm_pmr_zero_everything(void) 233 { 234 struct uvm_pmemrange *pmr; 235 struct vm_page *pg; 236 int i; 237 238 uvm_lock_fpageq(); 239 TAILQ_FOREACH(pmr, &uvm.pmr_control.use, pmr_use) { 240 /* Zero single pages. */ 241 while ((pg = TAILQ_FIRST(&pmr->single[UVM_PMR_MEMTYPE_DIRTY])) 242 != NULL) { 243 uvm_pmr_remove(pmr, pg); 244 uvm_pagezero(pg); 245 atomic_setbits_int(&pg->pg_flags, PG_ZERO); 246 uvmexp.zeropages++; 247 uvm_pmr_insert(pmr, pg, 0); 248 } 249 250 /* Zero multi page ranges. */ 251 while ((pg = RB_ROOT(&pmr->size[UVM_PMR_MEMTYPE_DIRTY])) 252 != NULL) { 253 pg--; /* Size tree always has second page. */ 254 uvm_pmr_remove(pmr, pg); 255 for (i = 0; i < pg->fpgsz; i++) { 256 uvm_pagezero(&pg[i]); 257 atomic_setbits_int(&pg[i].pg_flags, PG_ZERO); 258 uvmexp.zeropages++; 259 } 260 uvm_pmr_insert(pmr, pg, 0); 261 } 262 } 263 uvm_unlock_fpageq(); 264 } 265 266 /* 267 * Allocate the biggest contig chunk of memory. 268 */ 269 int 270 uvm_pmr_alloc_pig(paddr_t *addr, psize_t *sz) 271 { 272 struct uvm_pmemrange *pig_pmr, *pmr; 273 struct vm_page *pig_pg, *pg; 274 int memtype; 275 276 uvm_lock_fpageq(); 277 pig_pg = NULL; 278 TAILQ_FOREACH(pmr, &uvm.pmr_control.use, pmr_use) { 279 for (memtype = 0; memtype < UVM_PMR_MEMTYPE_MAX; memtype++) { 280 /* Find biggest page in this memtype pmr. */ 281 pg = RB_MAX(uvm_pmr_size, &pmr->size[memtype]); 282 if (pg == NULL) 283 pg = TAILQ_FIRST(&pmr->single[memtype]); 284 else 285 pg--; 286 287 if (pig_pg == NULL || (pg != NULL && pig_pg != NULL && 288 pig_pg->fpgsz < pg->fpgsz)) { 289 pig_pmr = pmr; 290 pig_pg = pg; 291 } 292 } 293 } 294 295 /* Remove page from freelist. */ 296 if (pig_pg != NULL) { 297 uvm_pmr_remove(pig_pmr, pig_pg); 298 uvmexp.free -= pig_pg->fpgsz; 299 if (pig_pg->pg_flags & PG_ZERO) 300 uvmexp.zeropages -= pig_pg->fpgsz; 301 *addr = VM_PAGE_TO_PHYS(pig_pg); 302 *sz = pig_pg->fpgsz; 303 } 304 uvm_unlock_fpageq(); 305 306 /* Return. */ 307 return (pig_pg != NULL ? 0 : ENOMEM); 308 } 309