ab0352d638893fc3c3ff8b83fbc661ca26febd82
[openafs.git] / src / afs / LINUX / osi_alloc.c
1 /*
2  * Copyright 2000, International Business Machines Corporation and others.
3  * All Rights Reserved.
4  * 
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
8  */
9
10 /*
11  * osi_alloc.c - Linux memory allocation routines.
12  *
13  */
14 #include "../afs/param.h"
15 #include "../afs/sysincludes.h"
16 #include "../afs/afsincludes.h"
17 #include "../h/mm.h"
18
19 #include "../afs/afs_atomlist.h"
20 #include "../afs/afs_lhash.h"
21
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*/
25
26 /* types of alloc */
27 #define KM_TYPE 1        /* kmalloc */
28 #define VM_TYPE 2        /* vmalloc */
29
30 struct osi_linux_mem {
31     void *chunk;
32 };
33
34 /* These assume 32-bit pointers */
35 #define MEMTYPE(A) (((unsigned int)A) & 0x3)
36 #define MEMADDR(A) (void *)((unsigned int)(A) & (~0x3))
37
38 /* globals */
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 */
47
48 #if defined(AFS_LINUX24_ENV)
49 #include "../h/vmalloc.h"
50 #else
51 /* externs : can we do this in a better way. Including vmalloc.h causes other
52  * problems.*/
53 extern void vfree(void * addr);
54 extern void *vmalloc(unsigned long size);
55 #endif
56
57 /* Allocator support functions (static) */
58
59 static int hash_equal(const void *a, const void *b) 
60 {
61     return ( MEMADDR(((struct osi_linux_mem *)a)->chunk) == 
62             MEMADDR(((struct osi_linux_mem *)b)->chunk) );
63
64 }
65
66 /* linux_alloc : Allocates memory from the linux kernel. It uses 
67  *               kmalloc if possible. Otherwise, we use vmalloc. 
68  * Input:
69  *  asize - size of memory required in bytes
70  * Return Values:
71  *  returns NULL if we failed to allocate memory.
72  *  or pointer to memory if we succeeded.
73  */
74 static void *linux_alloc(unsigned int asize)
75 {
76     void *new = NULL;
77     int has_afs_glock = ISAFS_GLOCK();
78
79     /* if global lock has been held save this info and unlock it. */
80     if (has_afs_glock)
81         AFS_GUNLOCK();
82
83     /*  if we can use kmalloc use it to allocate the required memory. */
84     if (asize <  MAX_KMALLOC_SIZE) {
85         new = (void *)kmalloc(asize, GFP_KERNEL);
86         if (new) /* piggy back alloc type */
87             (unsigned int)new |= KM_TYPE;
88     }
89     if (!new) { /* otherwise use vmalloc  */
90         int max_wait = 10;
91         while (!(new = (void *)vmalloc(asize))) {
92             if (--max_wait <=0) {
93                 break;
94             }
95             schedule();
96         }
97         if (new) /* piggy back alloc type */
98             (unsigned int)new |= VM_TYPE;
99     }
100     if (new)
101         memset(MEMADDR(new), 0, asize);
102
103     /* if the global lock had been held, lock it again. */
104     if (has_afs_glock)
105         AFS_GLOCK();
106
107     return new;
108 }
109
110 static void linux_free(void *p)
111 {
112     
113     /* mask out the type information from the pointer and
114      *  use the appropriate free routine to free the chunk.
115      */
116     switch(MEMTYPE(p)) {
117       case KM_TYPE:
118         kfree(MEMADDR(p));
119         break;
120       case VM_TYPE:
121         vfree(MEMADDR(p));
122         break;
123       default:
124         printf("afs_osi_Free: Asked to free unknown type %d at 0x%x\n",
125                MEMTYPE(p), MEMADDR(p));
126         break;
127     }
128
129 }
130
131 /* hash_chunk() receives a pointer to a chunk and hashes it to produce a
132  *            key that the hashtable can use. The key is obtained by 
133  *            right shifting out the 2 LSBs and then multiplying the
134  *            result by a constant no. and dividing it with a large prime.
135  */
136 #define HASH_CONST   32786
137 #define HASH_PRIME   79367
138 static unsigned hash_chunk(void *p)
139 {
140     unsigned int key;
141
142     key = (unsigned int)p >> 2;
143     key = (key * HASH_CONST)%HASH_PRIME;
144
145     return key;
146 }
147
148 /* hash_free() : Invoked by osi_linux_free_afs_memory(), thru 
149  *          afs_lhash_iter(), this function is called by the lhash
150  *          module for every entry in the hash table. hash_free
151  *          frees the memory associated with the entry as well
152  *          as returning the osi_linux_mem struct to its pool.
153  */
154 static void
155 hash_free(size_t index, unsigned key, void *data)
156 {
157     linux_free(((struct osi_linux_mem *)data)->chunk);
158     afs_atomlist_put(al_mem_pool, data);
159 }
160
161 /* hash_verify() is invoked by osi_linux_verify_alloced_memory() thru
162  *   afs_lhash_iter() and is called by the lhash module for every element
163  *   in the hash table. 
164  *  hash_verify() verifies (within limits) that the memory passed to it is
165  *  valid.
166  */
167 static void
168 hash_verify(size_t index, unsigned key, void *data)
169 {
170     struct osi_linux_mem *lmp = (struct osi_linux_mem *)data;
171     int memtype;
172
173     memtype = MEMTYPE(lmp->chunk);
174     if ((memtype == KM_TYPE) && (AFS_LINUX_MAP_NR(lmp->chunk) > max_mapnr)) {
175         printf("osi_linux_verify_alloced_memory: address 0x%x outside range, index=%d, key=%d\n", lmp->chunk, index, key);
176     }
177     
178     if (memtype != KM_TYPE && memtype != VM_TYPE) {
179         printf("osi_linux_verify_alloced_memory: unknown type %d at 0x%x, index=%d\n",    memtype, lmp->chunk, index);
180     }
181     afs_linux_hash_verify_count++;
182 }
183
184
185 /* local_free() : wrapper for vfree(), to deal with incompatible protoypes */
186 static void local_free(void *p, size_t n)
187 {
188     vfree(p);
189 }
190
191 /* linux_alloc_init(): Initializes the kernel memory allocator. As part
192  *    of this process, it also initializes a pool of osi_linux_mem
193  *    structures as well as the hash table itself.
194  *  Return values:
195  *    0 - failure
196  *    1 - success
197  */
198 static int linux_alloc_init()
199 {
200     /* initiate our pool of osi_linux_mem structs */
201     al_mem_pool = afs_atomlist_create(sizeof(struct osi_linux_mem),
202                                   sizeof(long)*1024, vmalloc, local_free);
203     if (!al_mem_pool) {
204         printf("afs_osi_Alloc: Error in initialization(atomlist_create)\n");
205         return 0;
206     }
207
208     /* initialize the hash table to hold references to alloc'ed chunks */
209     lh_mem_htab = afs_lhash_create(hash_equal, vmalloc, local_free);
210     if (!lh_mem_htab) {
211         printf("afs_osi_Alloc: Error in initialization(lhash_create)\n");
212         return 0;
213     }
214     
215     return 1;
216     
217 }
218
219 /* hash_bucket_stat() : Counts the no. of elements in each bucket and
220  *   stores results in our bucket stats vector.
221  */
222 static unsigned int cur_bucket, cur_bucket_len;
223 static void hash_bucket_stat(size_t index, unsigned key, void *data)
224 {
225     if (index == cur_bucket) { 
226         /* while still on the same bucket, inc len & return */
227         cur_bucket_len++;
228         return;
229     }
230     else { /* if we're on the next bucket, store the distribution */
231         if (cur_bucket_len < MAX_BUCKET_LEN)
232             afs_linux_hash_bucket_dist[cur_bucket_len]++;
233         else
234             printf("afs_get_hash_stats: Warning! exceeded max bucket len %d\n", cur_bucket_len);
235         cur_bucket = index;
236         cur_bucket_len = 1;
237     }
238 }
239 /* get_hash_stats() : get hash table statistics */
240 static void get_hash_stats()
241 {
242     int i;
243
244     afs_lhash_stat(lh_mem_htab, &afs_linux_lsb);
245
246     /* clear out the bucket stat vector */
247     for(i=0;i<MAX_BUCKET_LEN;i++, afs_linux_hash_bucket_dist[i]=0);
248     cur_bucket = cur_bucket_len = 00;
249
250     /* populate the bucket stat vector */
251     afs_lhash_iter(lh_mem_htab, hash_bucket_stat);
252 }
253
254 /************** Linux memory allocator interface functions **********/
255
256 #if defined(AFS_LINUX24_ENV)
257 DECLARE_MUTEX(afs_linux_alloc_sem);
258 #else
259 struct semaphore afs_linux_alloc_sem = MUTEX;
260 #endif
261
262 void *osi_linux_alloc(unsigned int asize)
263 {
264     void *new = NULL;
265     struct osi_linux_mem *lmem;
266
267     down(&afs_linux_alloc_sem);
268
269     if (allocator_init == 0) { /* allocator hasn't been initialized yet */
270         if (linux_alloc_init() == 0) {
271             goto error;
272          }
273         allocator_init = 1; /* initialization complete */
274     }
275
276     new = linux_alloc(asize); /* get a chunk of memory of size asize */
277     if (!new) {
278         printf("afs_osi_Alloc: Can't vmalloc %d bytes.\n", asize);
279         goto error;
280     }
281     
282     /* get an atom to store the pointer to the chunk */
283     lmem = (struct osi_linux_mem *)afs_atomlist_get(al_mem_pool);
284     if (!lmem) {
285         printf("afs_osi_Alloc: atomlist_get() failed.");
286         goto free_error;
287     }
288     /* store the chunk reference */
289     lmem->chunk = new;
290
291     /* hash in the chunk */
292     if (afs_lhash_enter(lh_mem_htab, hash_chunk(new), lmem) != 0) {
293         printf("afs_osi_Alloc: lhash_enter failed\n");
294         goto free_error;
295     }
296     afs_linux_cur_allocs++;   /* no. of current allocations */
297     afs_linux_total_allocs++; /* total no. of allocations done so far */
298     if ((afs_linux_cur_allocs % STAT_INTERVAL) == 0) {
299         get_hash_stats();
300     }
301   error:
302     up(&afs_linux_alloc_sem);
303     return MEMADDR(new);
304
305   free_error:
306     if (new)
307         linux_free(new);
308     new = NULL;
309     goto error;
310
311     
312 }
313
314 /* osi_linux_free() - free chunk of memory passed to us.
315  */
316 void osi_linux_free(void *addr)
317 {
318     struct osi_linux_mem lmem, *lmp;
319
320     down(&afs_linux_alloc_sem);
321     
322     lmem.chunk = addr;
323     /* remove this chunk from our hash table */
324     if ( lmp = (struct osi_linux_mem *)afs_lhash_remove(lh_mem_htab, hash_chunk(addr), &lmem)) {
325         linux_free(lmp->chunk); /* this contains the piggybacked type info*/
326         afs_atomlist_put(al_mem_pool, lmp); /* return osi_linux_mem struct to pool*/
327         afs_linux_cur_allocs--;
328     }
329     else   {
330         printf("osi_linux_free: failed to remove chunk from hashtable\n");
331     }
332
333     up(&afs_linux_alloc_sem);
334 }
335
336 /* osi_linux_free_afs_memory() - free all chunks of memory allocated.
337  */
338 void osi_linux_free_afs_memory(void)
339 {
340     down(&afs_linux_alloc_sem);
341
342     /* iterate through all elements in the hash table and free both 
343      * the chunk and the atom associated with it.
344      */
345     afs_lhash_iter(lh_mem_htab, hash_free);
346
347     /*  free the atomlist. */
348     afs_atomlist_destroy(al_mem_pool);
349
350     /* free the hashlist. */
351     afs_lhash_destroy(lh_mem_htab);
352
353     /* change the state so that the allocator is now uninitialized. */
354     allocator_init = 0;
355
356     up(&afs_linux_alloc_sem);    
357 }
358
359 /* osi_linux_verify_alloced_memory(): verify all chunks of alloced memory in
360  *          our hash table.
361  */
362 void osi_linux_verify_alloced_memory()
363 {
364     down(&afs_linux_alloc_sem);
365     
366     /* count of times hash_verify was called. reset it to 0 before iteration */
367     afs_linux_hash_verify_count = 0;
368
369     /* iterate thru elements in the hash table */
370     afs_lhash_iter(lh_mem_htab, hash_verify);
371
372     if (afs_linux_hash_verify_count != afs_linux_cur_allocs) {
373         /* hmm, some pieces of memory are missing. */
374         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);
375     }
376
377     up(&afs_linux_alloc_sem);
378     return;
379 }
380