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