2 * Copyright 2000, International Business Machines Corporation and others.
5 * This software has been released under the terms of the IBM Public
6 * License. For details, see the LICENSE file in the top-level source
7 * directory or online at http://www.openafs.org/dl/license10.html
11 * osi_alloc.c - Linux memory allocation routines.
14 #include "../afs/param.h"
15 #include "../afs/sysincludes.h"
16 #include "../afs/afsincludes.h"
19 #include "../afs/afs_atomlist.h"
20 #include "../afs/afs_lhash.h"
22 #define MAX_KMALLOC_SIZE (131072-16) /* Max we can alloc in physmem */
23 #define MAX_BUCKET_LEN 30 /* max. no. of entries per buckets we expect to see */
24 #define STAT_INTERVAL 8192 /* we collect stats once every STAT_INTERVAL allocs*/
27 #define KM_TYPE 1 /* kmalloc */
28 #define VM_TYPE 2 /* vmalloc */
30 struct osi_linux_mem {
34 /* These assume 32-bit pointers */
35 #define MEMTYPE(A) (((unsigned int)A) & 0x3)
36 #define MEMADDR(A) (void *)((unsigned int)(A) & (~0x3))
39 afs_atomlist *al_mem_pool; /* pool of osi_linux_mem structures */
40 afs_lhash *lh_mem_htab; /* mem hash table */
41 unsigned int allocator_init = 0; /* has the allocator been initialized? */
42 unsigned int afs_linux_cur_allocs = 0;
43 unsigned int afs_linux_total_allocs = 0;
44 unsigned int afs_linux_hash_verify_count = 0; /* used by hash_verify */
45 struct afs_lhash_stat afs_linux_lsb; /* hash table statistics */
46 unsigned int afs_linux_hash_bucket_dist[MAX_BUCKET_LEN]; /* bucket population distribution in our hash table */
48 /* externs : can we do this in a better way. Including vmalloc.h causes other
50 extern void vfree(void * addr);
51 extern void *vmalloc(unsigned long size);
53 /* Allocator support functions (static) */
55 static int hash_equal(const void *a, const void *b)
57 return ( MEMADDR(((struct osi_linux_mem *)a)->chunk) ==
58 MEMADDR(((struct osi_linux_mem *)b)->chunk) );
62 /* linux_alloc : Allocates memory from the linux kernel. It uses
63 * kmalloc if possible. Otherwise, we use vmalloc.
65 * asize - size of memory required in bytes
67 * returns NULL if we failed to allocate memory.
68 * or pointer to memory if we succeeded.
70 static void *linux_alloc(unsigned int asize)
73 int has_afs_glock = ISAFS_GLOCK();
75 /* if global lock has been held save this info and unlock it. */
79 /* if we can use kmalloc use it to allocate the required memory. */
80 if (asize < MAX_KMALLOC_SIZE) {
81 new = (void *)kmalloc(asize, GFP_KERNEL);
82 if (new) /* piggy back alloc type */
83 (unsigned int)new |= KM_TYPE;
85 if (!new) { /* otherwise use vmalloc */
87 while (!(new = (void *)vmalloc(asize))) {
93 if (new) /* piggy back alloc type */
94 (unsigned int)new |= VM_TYPE;
97 memset(MEMADDR(new), 0, asize);
99 /* if the global lock had been held, lock it again. */
106 static void linux_free(void *p)
109 /* mask out the type information from the pointer and
110 * use the appropriate free routine to free the chunk.
120 printf("afs_osi_Free: Asked to free unknown type %d at 0x%x\n",
121 MEMTYPE(p), MEMADDR(p));
127 /* hash_chunk() receives a pointer to a chunk and hashes it to produce a
128 * key that the hashtable can use. The key is obtained by
129 * right shifting out the 2 LSBs and then multiplying the
130 * result by a constant no. and dividing it with a large prime.
132 #define HASH_CONST 32786
133 #define HASH_PRIME 79367
134 static unsigned hash_chunk(void *p)
138 key = (unsigned int)p >> 2;
139 key = (key * HASH_CONST)%HASH_PRIME;
144 /* hash_free() : Invoked by osi_linux_free_afs_memory(), thru
145 * afs_lhash_iter(), this function is called by the lhash
146 * module for every entry in the hash table. hash_free
147 * frees the memory associated with the entry as well
148 * as returning the osi_linux_mem struct to its pool.
151 hash_free(size_t index, unsigned key, void *data)
153 linux_free(((struct osi_linux_mem *)data)->chunk);
154 afs_atomlist_put(al_mem_pool, data);
157 /* hash_verify() is invoked by osi_linux_verify_alloced_memory() thru
158 * afs_lhash_iter() and is called by the lhash module for every element
160 * hash_verify() verifies (within limits) that the memory passed to it is
164 hash_verify(size_t index, unsigned key, void *data)
166 struct osi_linux_mem *lmp = (struct osi_linux_mem *)data;
169 memtype = MEMTYPE(lmp->chunk);
170 if ((memtype == KM_TYPE) && (AFS_LINUX_MAP_NR(lmp->chunk) > max_mapnr)) {
171 printf("osi_linux_verify_alloced_memory: address 0x%x outside range, index=%d, key=%d\n", lmp->chunk, index, key);
174 if (memtype != KM_TYPE && memtype != VM_TYPE) {
175 printf("osi_linux_verify_alloced_memory: unknown type %d at 0x%x, index=%d\n", memtype, lmp->chunk, index);
177 afs_linux_hash_verify_count++;
181 /* local_free() : wrapper for vfree(), to deal with incompatible protoypes */
182 static void local_free(void *p, size_t n)
187 /* linux_alloc_init(): Initializes the kernel memory allocator. As part
188 * of this process, it also initializes a pool of osi_linux_mem
189 * structures as well as the hash table itself.
194 static int linux_alloc_init()
196 /* initiate our pool of osi_linux_mem structs */
197 al_mem_pool = afs_atomlist_create(sizeof(struct osi_linux_mem),
198 sizeof(long)*1024, vmalloc, local_free);
200 printf("afs_osi_Alloc: Error in initialization(atomlist_create)\n");
204 /* initialize the hash table to hold references to alloc'ed chunks */
205 lh_mem_htab = afs_lhash_create(hash_equal, vmalloc, local_free);
207 printf("afs_osi_Alloc: Error in initialization(lhash_create)\n");
215 /* hash_bucket_stat() : Counts the no. of elements in each bucket and
216 * stores results in our bucket stats vector.
218 static unsigned int cur_bucket, cur_bucket_len;
219 static void hash_bucket_stat(size_t index, unsigned key, void *data)
221 if (index == cur_bucket) {
222 /* while still on the same bucket, inc len & return */
226 else { /* if we're on the next bucket, store the distribution */
227 if (cur_bucket_len < MAX_BUCKET_LEN)
228 afs_linux_hash_bucket_dist[cur_bucket_len]++;
230 printf("afs_get_hash_stats: Warning! exceeded max bucket len %d\n", cur_bucket_len);
235 /* get_hash_stats() : get hash table statistics */
236 static void get_hash_stats()
240 afs_lhash_stat(lh_mem_htab, &afs_linux_lsb);
242 /* clear out the bucket stat vector */
243 for(i=0;i<MAX_BUCKET_LEN;i++, afs_linux_hash_bucket_dist[i]=0);
244 cur_bucket = cur_bucket_len = 00;
246 /* populate the bucket stat vector */
247 afs_lhash_iter(lh_mem_htab, hash_bucket_stat);
250 /************** Linux memory allocator interface functions **********/
252 struct semaphore afs_linux_alloc_sem = MUTEX;
254 void *osi_linux_alloc(unsigned int asize)
257 struct osi_linux_mem *lmem;
259 down(&afs_linux_alloc_sem);
261 if (allocator_init == 0) { /* allocator hasn't been initialized yet */
262 if (linux_alloc_init() == 0) {
265 allocator_init = 1; /* initialization complete */
268 new = linux_alloc(asize); /* get a chunk of memory of size asize */
270 printf("afs_osi_Alloc: Can't vmalloc %d bytes.\n", asize);
274 /* get an atom to store the pointer to the chunk */
275 lmem = (struct osi_linux_mem *)afs_atomlist_get(al_mem_pool);
277 printf("afs_osi_Alloc: atomlist_get() failed.");
280 /* store the chunk reference */
283 /* hash in the chunk */
284 if (afs_lhash_enter(lh_mem_htab, hash_chunk(new), lmem) != 0) {
285 printf("afs_osi_Alloc: lhash_enter failed\n");
288 afs_linux_cur_allocs++; /* no. of current allocations */
289 afs_linux_total_allocs++; /* total no. of allocations done so far */
290 if ((afs_linux_cur_allocs % STAT_INTERVAL) == 0) {
294 up(&afs_linux_alloc_sem);
306 /* osi_linux_free() - free chunk of memory passed to us.
308 void osi_linux_free(void *addr)
310 struct osi_linux_mem lmem, *lmp;
312 down(&afs_linux_alloc_sem);
315 /* remove this chunk from our hash table */
316 if ( lmp = (struct osi_linux_mem *)afs_lhash_remove(lh_mem_htab, hash_chunk(addr), &lmem)) {
317 linux_free(lmp->chunk); /* this contains the piggybacked type info*/
318 afs_atomlist_put(al_mem_pool, lmp); /* return osi_linux_mem struct to pool*/
319 afs_linux_cur_allocs--;
322 printf("osi_linux_free: failed to remove chunk from hashtable\n");
325 up(&afs_linux_alloc_sem);
328 /* osi_linux_free_afs_memory() - free all chunks of memory allocated.
330 void osi_linux_free_afs_memory(void)
332 down(&afs_linux_alloc_sem);
334 /* iterate through all elements in the hash table and free both
335 * the chunk and the atom associated with it.
337 afs_lhash_iter(lh_mem_htab, hash_free);
339 /* free the atomlist. */
340 afs_atomlist_destroy(al_mem_pool);
342 /* free the hashlist. */
343 afs_lhash_destroy(lh_mem_htab);
345 /* change the state so that the allocator is now uninitialized. */
348 up(&afs_linux_alloc_sem);
351 /* osi_linux_verify_alloced_memory(): verify all chunks of alloced memory in
354 void osi_linux_verify_alloced_memory()
356 down(&afs_linux_alloc_sem);
358 /* count of times hash_verify was called. reset it to 0 before iteration */
359 afs_linux_hash_verify_count = 0;
361 /* iterate thru elements in the hash table */
362 afs_lhash_iter(lh_mem_htab, hash_verify);
364 if (afs_linux_hash_verify_count != afs_linux_cur_allocs) {
365 /* hmm, some pieces of memory are missing. */
366 printf("osi_linux_verify_alloced_memory: %d chunks of memory are not accounted for during verify!\n", afs_linux_hash_verify_count - afs_linux_cur_allocs);
369 up(&afs_linux_alloc_sem);