xref: /openbsd-src/sys/kern/subr_hibernate.c (revision 088aa6da3d5d18133795f547ea511607f2aad1c6)
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