xref: /minix/minix/lib/libddekit/src/mem.c (revision 7f5f010b) 
1 #include "common.h"
2 
3 #include <ddekit/lock.h>
4 #include <ddekit/memory.h>
5 #include <ddekit/panic.h>
6 #include <ddekit/pgtab.h>
7 #include <ddekit/inline.h>
8 #include <ddekit/types.h>
9 
10 #ifdef DDEKIT_DEBUG_MEM
11 #undef DDEBUG
12 #define DDEBUG DDEKIT_DEBUG_MEM
13 #endif
14 #include "debug.h"
15 #include "util.h"
16 
17 #define SLAB_SIZE (4096*4)
18 
19 struct ddekit_slab;
20 
21 struct ddekit_slab_slab {
22 	struct ddekit_slab * cache;
23 	unsigned long free;
24 	void *objects;
25 	void *mem;
26 	struct ddekit_slab_slab *next;
27 	struct ddekit_slab_slab *prev;
28 };
29 
30 struct ddekit_slab {
31 	ddekit_lock_t lock;
32 	void * data;    /* user pointer */
33 	int contiguous; /* is it coniguous mem*/
34 	unsigned size;  /* the size of he objects */
35 	unsigned number; /* the number of objects stored per slab */
36 	struct ddekit_slab_slab full;
37 	struct ddekit_slab_slab partial;
38 	struct ddekit_slab_slab empty;
39 };
40 
41 static void ddekit_slab_lock(struct ddekit_slab * sc);
42 static void ddekit_slab_unlock(struct ddekit_slab * sc);
43 static struct ddekit_slab_slab * ddekit_slab_find_slab(struct
44 	ddekit_slab * sc, void * obj);
45 static void ddekit_slab_slab_insert(struct ddekit_slab_slab *list,
46 	struct ddekit_slab_slab *s);
47 static void ddekit_slab_slab_remove(struct ddekit_slab_slab *s);
48 static void ddekit_slab_grow(struct ddekit_slab * sc);
49 static void *ddekit_slab_getobj(struct ddekit_slab_slab *s);
50 static void ddekit_slab_free_slab(struct ddekit_slab_slab * sl, int
51 	cont);
52 
53 /******************************************************************************
54  *       ddekit_simple_malloc                                                 *
55  *****************************************************************************/
56 void *ddekit_simple_malloc(unsigned size)
57 {
58 	/* Simple memory allocation... malloc and free should be ok... */
59 	void * r = malloc(size);
60 	if (!r) {
61 		ddekit_panic("out of mem?");
62 	}
63 	DDEBUG_MSG_VERBOSE("%p", r);
64 	return r;
65 }
66 
67 /******************************************************************************
68  *       ddekit_simple_free                                                   *
69  *****************************************************************************/
70 void ddekit_simple_free(void *p)
71 {
72 	DDEBUG_MSG_VERBOSE("%p", p);
73 	free(p);
74 }
75 
76 /******************************************************************************
77  *       ddekit_large_malloc                                                  *
78  *****************************************************************************/
79 void *ddekit_large_malloc(int size)
80 {
81 	ddekit_addr_t phys;
82 	/* allocate a piece of coniguous memory */
83 	void * r = alloc_contig(size, AC_ALIGN4K, &phys);
84 	if (!r) {
85 		ddekit_panic("out of mem?");
86 	}
87 	ddekit_pgtab_set_region_with_size(r, phys, size, PTE_TYPE_LARGE);
88 	DDEBUG_MSG_VERBOSE("%p, phys: %p, size: %p.",r, phys, size);
89 	DDEBUG_MSG_VERBOSE("%p", r);
90 	return r;
91 }
92 
93 /******************************************************************************
94  *       ddekit_large_free                                                    *
95  *****************************************************************************/
96 void ddekit_large_free(void *p)
97 {
98 	unsigned len;
99 	DDEBUG_MSG_VERBOSE("get size of region %x", p);
100 	len= ddekit_pgtab_get_size(p);
101 	DDEBUG_MSG_VERBOSE("freeing %x, len %d...", p , len);
102 	ddekit_pgtab_clear_region(p, 0); /* type is not used here... */
103 	DDEBUG_MSG_VERBOSE("cleared region", p , len);
104 	free_contig(p, len);
105 	DDEBUG_MSG_VERBOSE("freed mem", p , len);
106 	DDEBUG_MSG_VERBOSE("%p", p);
107 }
108 
109 /******************************************************************************
110  *       ddekit_contig_malloc                                                 *
111  *****************************************************************************/
112 void *ddekit_contig_malloc(unsigned long size, unsigned long low,
113                                   unsigned long high, unsigned long aligment,
114                                   unsigned long boundary)
115 {
116 	WARN_UNIMPL;
117 	return 0;
118 }
119 
120 /******************************************************************************
121  *       ddekit_slab_lock                                                     *
122  *****************************************************************************/
123 static DDEKIT_INLINE void ddekit_slab_lock(struct ddekit_slab * sc) {
124 	ddekit_lock_lock(&sc->lock);
125 }
126 
127 /******************************************************************************
128  *       ddekit_slab_unlock                                                   *
129  *****************************************************************************/
130 static DDEKIT_INLINE void ddekit_slab_unlock(struct ddekit_slab * sc) {
131 	ddekit_lock_unlock(&sc->lock);
132 }
133 
134 /******************************************************************************
135  *       ddekit_slab_find_slab                                                *
136  *****************************************************************************/
137 static struct ddekit_slab_slab *
138 ddekit_slab_find_slab(struct ddekit_slab * sc, void * obj)
139 {
140 
141 	struct ddekit_slab_slab *s;
142 
143 	for( s = sc->full.next; s!=&sc->full; s = s->next )
144 	{
145 		if (s->mem <= obj && obj < s->mem+(SLAB_SIZE))
146 		{
147 				return s;
148 		}
149 	}
150 
151 	for( s = sc->partial.next; s!=&sc->partial; s = s->next )
152 	{
153 		if (s->mem <= obj && obj < s->mem+(SLAB_SIZE))
154 		{
155 				return s;
156 		}
157 	}
158 
159 	return 0;
160 }
161 
162 /******************************************************************************
163  *       ddekit_slab_slab_insert                                              *
164  *****************************************************************************/
165 static void  ddekit_slab_slab_insert(struct ddekit_slab_slab *list,
166                                       struct ddekit_slab_slab *s)
167 {
168 	s->prev          = list;
169 	s->next          = list->next;
170 	list->next->prev = s;
171 	list->next       = s;
172 }
173 
174 /******************************************************************************
175  *       ddekit_slab_slab_remove                                              *
176  *****************************************************************************/
177 static void ddekit_slab_slab_remove(struct ddekit_slab_slab *s)
178 {
179 	s->next->prev     = s->prev;
180 	s->prev->next     = s->next;
181 	s->next = s->prev = 0;
182 }
183 
184 
185 /******************************************************************************
186  *       ddekit_slab_grow                                                     *
187  *****************************************************************************/
188 static void ddekit_slab_grow(struct ddekit_slab *sc)
189 {
190 	/*
191 	 * NOTE:
192 	 * As it doesn't seem to make problems ddekit_slabs are disregarding
193 	 * alignment.  However this should be revisited, maybe this leads to
194 	 * performance degregation somewhere.
195 	 * Further the ddekit_slab doesn't have to be real slab, as the entries are
196 	 * initialized in the personalized DDEs. (slab is simple the wrong name.)
197 	 */
198 	int i;
199 	char *p;
200 	void **p1;
201 	struct ddekit_slab_slab *s;
202 
203 	/* allocate slab control structure */
204 
205 	s = (struct ddekit_slab_slab *)
206 	    ddekit_simple_malloc(sizeof(struct ddekit_slab_slab));
207 
208 	s->cache = sc;
209 
210 	if(sc->contiguous)
211 		s->mem = ddekit_large_malloc(SLAB_SIZE);
212 	else
213 		s->mem = ddekit_simple_malloc(SLAB_SIZE);
214 
215 	/* setup the object list */
216 
217 	s->free = sc->number;
218 
219 	/* put obj into list */
220 	p1 = s->mem;
221 	*p1 = s->mem;
222 	s->objects =  p1;
223 
224 	DDEBUG_MSG_VERBOSE("obj size: %d, memory at: %p , first obj: %p, %p ",
225 	                    sc->size, s->mem, s->objects);
226 
227 	for (i = 0; i < s->free; i++)
228 	{
229 		p  = *p1;
230 		p1 = (void **) (p + sc->size);
231 
232 		if ( i != s->free-1 )
233 		{
234 			*p1 = p1+1;
235 			DDEBUG_MSG_VERBOSE("%p, %p -> %p", p, p1, *p1);
236 		}
237 		else
238 		{
239 			*p1 = 0;
240 			DDEBUG_MSG_VERBOSE("%p, %p -> %p", p, p1, *p1);
241 		}
242 	}
243 
244 	/* add new slab to free list */
245 	ddekit_slab_slab_insert(&sc->empty, s);
246 }
247 
248 
249 /******************************************************************************
250  *       ddekit_slab_getobj                                                   *
251  *****************************************************************************/
252 static void *ddekit_slab_getobj(struct ddekit_slab_slab *s)
253 {
254 	struct ddekit_slab *sc;
255 	void *ret = 0;
256 
257 	sc = s->cache;
258 	ret  = s->objects;
259 
260 	/* get pointer to next object */
261 
262 	s->objects = *(void **)((char *) ret + sc->size);
263 	s->free--;
264 
265 	DDEBUG_MSG_VERBOSE("old: %p new: %p", ret, s->objects);
266 
267 	/* if no more objects move to full */
268 
269 	if (!s->free)
270 	{
271 		ddekit_slab_slab_remove(s);
272 		ddekit_slab_slab_insert(&sc->full,s);
273 	}
274 
275 	if (s->free == sc->number-1)
276 	{
277 		ddekit_slab_slab_remove(s);
278 		ddekit_slab_slab_insert(&sc->partial,s);
279 	}
280 
281 	return ret;
282 }
283 
284 /******************************************************************************
285  *       ddekit_slab_alloc                                                    *
286  *****************************************************************************/
287 void *ddekit_slab_alloc(struct ddekit_slab * sc)
288 {
289 	struct ddekit_slab_slab *s=0;
290 
291 	ddekit_slab_lock(sc);
292 
293 	DDEBUG_MSG_VERBOSE("from slab %p", sc);
294 
295 	/* first try from partial */
296 	if (sc->partial.next != &sc->partial) {
297 		DDEBUG_MSG_VERBOSE("from slab %p partial (next=%p)", sc,sc->partial.next);
298 		s = sc->partial.next;
299 	}
300 
301 	/* must grow? */
302 	if (!s && (sc->empty.next == &sc->empty )){
303 		DDEBUG_MSG_VERBOSE("slab %p has to grow", sc);
304 		ddekit_slab_grow(sc);
305 	}
306 
307 	/* take from free? */
308 	if (!s) {
309 		DDEBUG_MSG_VERBOSE("from slab %p empty", sc);
310 		s = sc->empty.next;
311 	}
312 
313 	ddekit_slab_unlock(sc);
314 
315 	return ddekit_slab_getobj(s);
316 }
317 
318 /******************************************************************************
319  *       ddekit_slab_free                                                     *
320  *****************************************************************************/
321 void ddekit_slab_free(struct ddekit_slab *sc, void* obj)
322 {
323 	void **p;
324 
325 	struct ddekit_slab_slab *s = 0;
326 
327 	ddekit_slab_lock(sc);
328 	/* first find slab the obj came from */
329 
330 	s = ddekit_slab_find_slab(sc, obj);
331 
332 	p = (void **)((char *) obj + sc->size);
333 
334 	*p= s->objects;
335 	s->objects=obj;
336 
337 	DDEBUG_MSG_VERBOSE("old: %p, new: %p",*p,s->objects );
338 
339 	s->free++;
340 
341 	if (s->free == sc->number) {
342 		ddekit_slab_slab_remove(s);
343 		ddekit_slab_slab_insert(&sc->empty, s);
344 	}
345 
346 	if (s->free == 1) {
347 		ddekit_slab_slab_remove(s);
348 		ddekit_slab_slab_insert(&sc->partial, s);
349 	}
350 
351 	ddekit_slab_unlock(sc);
352 }
353 
354 /******************************************************************************
355  *       ddekit_slab_set_data                                                 *
356  *****************************************************************************/
357 void ddekit_slab_set_data(struct ddekit_slab * sc, void *data)
358 {
359 	ddekit_slab_lock(sc);
360 	sc->data = data;
361 	ddekit_slab_unlock(sc);
362 }
363 
364 /******************************************************************************
365  *       ddekit_slab_get_data                                                 *
366  *****************************************************************************/
367 void *ddekit_slab_get_data (struct ddekit_slab *sc)
368 {
369 	void *ret;
370 	ddekit_slab_lock(sc);
371 	ret=sc->data;
372 	ddekit_slab_unlock(sc);
373 	return ret;
374 }
375 
376 
377 /******************************************************************************
378  *       ddekit_slab_init                                                     *
379  *****************************************************************************/
380 struct ddekit_slab * ddekit_slab_init(unsigned size, int contiguous)
381 {
382 
383 	struct ddekit_slab * sc = 0;
384 
385 	sc = (struct ddekit_slab *)
386 	    ddekit_simple_malloc(sizeof(struct ddekit_slab));
387 
388 	sc->data       = 0;
389 	sc->contiguous = contiguous;
390 	sc->size       = size;
391 	sc->number     = SLAB_SIZE/(size+sizeof(void*));
392 
393 	if (sc->number == 0) {
394 		ddekit_panic("objects too big!");
395 	}
396 
397 	sc->empty.next   = sc->empty.prev   = &sc->empty;
398 	sc->partial.next = sc->partial.prev = &sc->partial;
399 	sc->full.next    = sc->full.prev    = &sc->full;
400 
401 	ddekit_lock_init(&sc->lock);
402 
403 	DDEBUG_MSG_VERBOSE("initialzed slab cache %p: size %x, number %d ",
404 	    sc, sc->size, sc->number);
405 
406 	DDEBUG_MSG_VERBOSE("partial %p next %p", &sc->partial, sc->partial.next);
407 	return sc ;
408 
409 }
410 
411 
412 /******************************************************************************
413  *       ddekit_slab_free_slab                                                *
414  *****************************************************************************/
415 static void ddekit_slab_free_slab(struct ddekit_slab_slab * sl, int cont)
416 {
417 
418 	struct ddekit_slab_slab *s,*t;
419 
420 	if (!sl) {
421 		ddekit_panic("no slab to free!");
422 	}
423 
424 	for ( s = sl->next; s != sl; )
425 	{
426 		DDEBUG_MSG_VERBOSE("cont: %d, %p, s->mem", cont, s->mem);
427 		if(cont)
428 		{
429 			ddekit_large_free(s->mem);
430 		}
431 		else
432 		{
433 			ddekit_simple_free(s->mem);
434 		}
435 		t = s;
436 		s = s->next;
437 		ddekit_simple_free(t);
438 	}
439 
440 }
441 
442 /******************************************************************************
443  *       ddekit_slab_destroy                                                  *
444  *****************************************************************************/
445 void ddekit_slab_destroy(struct ddekit_slab *sc)
446 {
447 	DDEBUG_MSG_VERBOSE("%p full", sc);
448 	ddekit_slab_free_slab(&sc->full,sc->contiguous);
449 
450 	DDEBUG_MSG_VERBOSE("%p empty", sc);
451 	ddekit_slab_free_slab(&sc->empty,sc->contiguous);
452 
453 	DDEBUG_MSG_VERBOSE("%p partial", sc);
454 	ddekit_slab_free_slab(&sc->partial,sc->contiguous);
455 
456 	ddekit_lock_deinit(&sc->lock);
457 
458 	ddekit_simple_free(sc);
459 }
460