[PATCH] lockdep: better lock debugging
[linux-2.6.git] / mm / vmalloc.c
1 /*
2  *  linux/mm/vmalloc.c
3  *
4  *  Copyright (C) 1993  Linus Torvalds
5  *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
6  *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
7  *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
8  *  Numa awareness, Christoph Lameter, SGI, June 2005
9  */
10
11 #include <linux/mm.h>
12 #include <linux/module.h>
13 #include <linux/highmem.h>
14 #include <linux/slab.h>
15 #include <linux/spinlock.h>
16 #include <linux/interrupt.h>
17
18 #include <linux/vmalloc.h>
19
20 #include <asm/uaccess.h>
21 #include <asm/tlbflush.h>
22
23
24 DEFINE_RWLOCK(vmlist_lock);
25 struct vm_struct *vmlist;
26
27 static void vunmap_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end)
28 {
29         pte_t *pte;
30
31         pte = pte_offset_kernel(pmd, addr);
32         do {
33                 pte_t ptent = ptep_get_and_clear(&init_mm, addr, pte);
34                 WARN_ON(!pte_none(ptent) && !pte_present(ptent));
35         } while (pte++, addr += PAGE_SIZE, addr != end);
36 }
37
38 static inline void vunmap_pmd_range(pud_t *pud, unsigned long addr,
39                                                 unsigned long end)
40 {
41         pmd_t *pmd;
42         unsigned long next;
43
44         pmd = pmd_offset(pud, addr);
45         do {
46                 next = pmd_addr_end(addr, end);
47                 if (pmd_none_or_clear_bad(pmd))
48                         continue;
49                 vunmap_pte_range(pmd, addr, next);
50         } while (pmd++, addr = next, addr != end);
51 }
52
53 static inline void vunmap_pud_range(pgd_t *pgd, unsigned long addr,
54                                                 unsigned long end)
55 {
56         pud_t *pud;
57         unsigned long next;
58
59         pud = pud_offset(pgd, addr);
60         do {
61                 next = pud_addr_end(addr, end);
62                 if (pud_none_or_clear_bad(pud))
63                         continue;
64                 vunmap_pmd_range(pud, addr, next);
65         } while (pud++, addr = next, addr != end);
66 }
67
68 void unmap_vm_area(struct vm_struct *area)
69 {
70         pgd_t *pgd;
71         unsigned long next;
72         unsigned long addr = (unsigned long) area->addr;
73         unsigned long end = addr + area->size;
74
75         BUG_ON(addr >= end);
76         pgd = pgd_offset_k(addr);
77         flush_cache_vunmap(addr, end);
78         do {
79                 next = pgd_addr_end(addr, end);
80                 if (pgd_none_or_clear_bad(pgd))
81                         continue;
82                 vunmap_pud_range(pgd, addr, next);
83         } while (pgd++, addr = next, addr != end);
84         flush_tlb_kernel_range((unsigned long) area->addr, end);
85 }
86
87 static int vmap_pte_range(pmd_t *pmd, unsigned long addr,
88                         unsigned long end, pgprot_t prot, struct page ***pages)
89 {
90         pte_t *pte;
91
92         pte = pte_alloc_kernel(pmd, addr);
93         if (!pte)
94                 return -ENOMEM;
95         do {
96                 struct page *page = **pages;
97                 WARN_ON(!pte_none(*pte));
98                 if (!page)
99                         return -ENOMEM;
100                 set_pte_at(&init_mm, addr, pte, mk_pte(page, prot));
101                 (*pages)++;
102         } while (pte++, addr += PAGE_SIZE, addr != end);
103         return 0;
104 }
105
106 static inline int vmap_pmd_range(pud_t *pud, unsigned long addr,
107                         unsigned long end, pgprot_t prot, struct page ***pages)
108 {
109         pmd_t *pmd;
110         unsigned long next;
111
112         pmd = pmd_alloc(&init_mm, pud, addr);
113         if (!pmd)
114                 return -ENOMEM;
115         do {
116                 next = pmd_addr_end(addr, end);
117                 if (vmap_pte_range(pmd, addr, next, prot, pages))
118                         return -ENOMEM;
119         } while (pmd++, addr = next, addr != end);
120         return 0;
121 }
122
123 static inline int vmap_pud_range(pgd_t *pgd, unsigned long addr,
124                         unsigned long end, pgprot_t prot, struct page ***pages)
125 {
126         pud_t *pud;
127         unsigned long next;
128
129         pud = pud_alloc(&init_mm, pgd, addr);
130         if (!pud)
131                 return -ENOMEM;
132         do {
133                 next = pud_addr_end(addr, end);
134                 if (vmap_pmd_range(pud, addr, next, prot, pages))
135                         return -ENOMEM;
136         } while (pud++, addr = next, addr != end);
137         return 0;
138 }
139
140 int map_vm_area(struct vm_struct *area, pgprot_t prot, struct page ***pages)
141 {
142         pgd_t *pgd;
143         unsigned long next;
144         unsigned long addr = (unsigned long) area->addr;
145         unsigned long end = addr + area->size - PAGE_SIZE;
146         int err;
147
148         BUG_ON(addr >= end);
149         pgd = pgd_offset_k(addr);
150         do {
151                 next = pgd_addr_end(addr, end);
152                 err = vmap_pud_range(pgd, addr, next, prot, pages);
153                 if (err)
154                         break;
155         } while (pgd++, addr = next, addr != end);
156         flush_cache_vmap((unsigned long) area->addr, end);
157         return err;
158 }
159
160 struct vm_struct *__get_vm_area_node(unsigned long size, unsigned long flags,
161                                 unsigned long start, unsigned long end, int node)
162 {
163         struct vm_struct **p, *tmp, *area;
164         unsigned long align = 1;
165         unsigned long addr;
166
167         if (flags & VM_IOREMAP) {
168                 int bit = fls(size);
169
170                 if (bit > IOREMAP_MAX_ORDER)
171                         bit = IOREMAP_MAX_ORDER;
172                 else if (bit < PAGE_SHIFT)
173                         bit = PAGE_SHIFT;
174
175                 align = 1ul << bit;
176         }
177         addr = ALIGN(start, align);
178         size = PAGE_ALIGN(size);
179
180         area = kmalloc_node(sizeof(*area), GFP_KERNEL, node);
181         if (unlikely(!area))
182                 return NULL;
183
184         if (unlikely(!size)) {
185                 kfree (area);
186                 return NULL;
187         }
188
189         /*
190          * We always allocate a guard page.
191          */
192         size += PAGE_SIZE;
193
194         write_lock(&vmlist_lock);
195         for (p = &vmlist; (tmp = *p) != NULL ;p = &tmp->next) {
196                 if ((unsigned long)tmp->addr < addr) {
197                         if((unsigned long)tmp->addr + tmp->size >= addr)
198                                 addr = ALIGN(tmp->size + 
199                                              (unsigned long)tmp->addr, align);
200                         continue;
201                 }
202                 if ((size + addr) < addr)
203                         goto out;
204                 if (size + addr <= (unsigned long)tmp->addr)
205                         goto found;
206                 addr = ALIGN(tmp->size + (unsigned long)tmp->addr, align);
207                 if (addr > end - size)
208                         goto out;
209         }
210
211 found:
212         area->next = *p;
213         *p = area;
214
215         area->flags = flags;
216         area->addr = (void *)addr;
217         area->size = size;
218         area->pages = NULL;
219         area->nr_pages = 0;
220         area->phys_addr = 0;
221         write_unlock(&vmlist_lock);
222
223         return area;
224
225 out:
226         write_unlock(&vmlist_lock);
227         kfree(area);
228         if (printk_ratelimit())
229                 printk(KERN_WARNING "allocation failed: out of vmalloc space - use vmalloc=<size> to increase size.\n");
230         return NULL;
231 }
232
233 struct vm_struct *__get_vm_area(unsigned long size, unsigned long flags,
234                                 unsigned long start, unsigned long end)
235 {
236         return __get_vm_area_node(size, flags, start, end, -1);
237 }
238
239 /**
240  *      get_vm_area  -  reserve a contingous kernel virtual area
241  *
242  *      @size:          size of the area
243  *      @flags:         %VM_IOREMAP for I/O mappings or VM_ALLOC
244  *
245  *      Search an area of @size in the kernel virtual mapping area,
246  *      and reserved it for out purposes.  Returns the area descriptor
247  *      on success or %NULL on failure.
248  */
249 struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
250 {
251         return __get_vm_area(size, flags, VMALLOC_START, VMALLOC_END);
252 }
253
254 struct vm_struct *get_vm_area_node(unsigned long size, unsigned long flags, int node)
255 {
256         return __get_vm_area_node(size, flags, VMALLOC_START, VMALLOC_END, node);
257 }
258
259 /* Caller must hold vmlist_lock */
260 static struct vm_struct *__find_vm_area(void *addr)
261 {
262         struct vm_struct *tmp;
263
264         for (tmp = vmlist; tmp != NULL; tmp = tmp->next) {
265                  if (tmp->addr == addr)
266                         break;
267         }
268
269         return tmp;
270 }
271
272 /* Caller must hold vmlist_lock */
273 struct vm_struct *__remove_vm_area(void *addr)
274 {
275         struct vm_struct **p, *tmp;
276
277         for (p = &vmlist ; (tmp = *p) != NULL ;p = &tmp->next) {
278                  if (tmp->addr == addr)
279                          goto found;
280         }
281         return NULL;
282
283 found:
284         unmap_vm_area(tmp);
285         *p = tmp->next;
286
287         /*
288          * Remove the guard page.
289          */
290         tmp->size -= PAGE_SIZE;
291         return tmp;
292 }
293
294 /**
295  *      remove_vm_area  -  find and remove a contingous kernel virtual area
296  *
297  *      @addr:          base address
298  *
299  *      Search for the kernel VM area starting at @addr, and remove it.
300  *      This function returns the found VM area, but using it is NOT safe
301  *      on SMP machines, except for its size or flags.
302  */
303 struct vm_struct *remove_vm_area(void *addr)
304 {
305         struct vm_struct *v;
306         write_lock(&vmlist_lock);
307         v = __remove_vm_area(addr);
308         write_unlock(&vmlist_lock);
309         return v;
310 }
311
312 void __vunmap(void *addr, int deallocate_pages)
313 {
314         struct vm_struct *area;
315
316         if (!addr)
317                 return;
318
319         if ((PAGE_SIZE-1) & (unsigned long)addr) {
320                 printk(KERN_ERR "Trying to vfree() bad address (%p)\n", addr);
321                 WARN_ON(1);
322                 return;
323         }
324
325         area = remove_vm_area(addr);
326         if (unlikely(!area)) {
327                 printk(KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
328                                 addr);
329                 WARN_ON(1);
330                 return;
331         }
332
333         debug_check_no_locks_freed(addr, area->size);
334
335         if (deallocate_pages) {
336                 int i;
337
338                 for (i = 0; i < area->nr_pages; i++) {
339                         BUG_ON(!area->pages[i]);
340                         __free_page(area->pages[i]);
341                 }
342
343                 if (area->nr_pages > PAGE_SIZE/sizeof(struct page *))
344                         vfree(area->pages);
345                 else
346                         kfree(area->pages);
347         }
348
349         kfree(area);
350         return;
351 }
352
353 /**
354  *      vfree  -  release memory allocated by vmalloc()
355  *
356  *      @addr:          memory base address
357  *
358  *      Free the virtually contiguous memory area starting at @addr, as
359  *      obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is
360  *      NULL, no operation is performed.
361  *
362  *      Must not be called in interrupt context.
363  */
364 void vfree(void *addr)
365 {
366         BUG_ON(in_interrupt());
367         __vunmap(addr, 1);
368 }
369 EXPORT_SYMBOL(vfree);
370
371 /**
372  *      vunmap  -  release virtual mapping obtained by vmap()
373  *
374  *      @addr:          memory base address
375  *
376  *      Free the virtually contiguous memory area starting at @addr,
377  *      which was created from the page array passed to vmap().
378  *
379  *      Must not be called in interrupt context.
380  */
381 void vunmap(void *addr)
382 {
383         BUG_ON(in_interrupt());
384         __vunmap(addr, 0);
385 }
386 EXPORT_SYMBOL(vunmap);
387
388 /**
389  *      vmap  -  map an array of pages into virtually contiguous space
390  *
391  *      @pages:         array of page pointers
392  *      @count:         number of pages to map
393  *      @flags:         vm_area->flags
394  *      @prot:          page protection for the mapping
395  *
396  *      Maps @count pages from @pages into contiguous kernel virtual
397  *      space.
398  */
399 void *vmap(struct page **pages, unsigned int count,
400                 unsigned long flags, pgprot_t prot)
401 {
402         struct vm_struct *area;
403
404         if (count > num_physpages)
405                 return NULL;
406
407         area = get_vm_area((count << PAGE_SHIFT), flags);
408         if (!area)
409                 return NULL;
410         if (map_vm_area(area, prot, &pages)) {
411                 vunmap(area->addr);
412                 return NULL;
413         }
414
415         return area->addr;
416 }
417 EXPORT_SYMBOL(vmap);
418
419 void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
420                                 pgprot_t prot, int node)
421 {
422         struct page **pages;
423         unsigned int nr_pages, array_size, i;
424
425         nr_pages = (area->size - PAGE_SIZE) >> PAGE_SHIFT;
426         array_size = (nr_pages * sizeof(struct page *));
427
428         area->nr_pages = nr_pages;
429         /* Please note that the recursion is strictly bounded. */
430         if (array_size > PAGE_SIZE)
431                 pages = __vmalloc_node(array_size, gfp_mask, PAGE_KERNEL, node);
432         else
433                 pages = kmalloc_node(array_size, (gfp_mask & ~__GFP_HIGHMEM), node);
434         area->pages = pages;
435         if (!area->pages) {
436                 remove_vm_area(area->addr);
437                 kfree(area);
438                 return NULL;
439         }
440         memset(area->pages, 0, array_size);
441
442         for (i = 0; i < area->nr_pages; i++) {
443                 if (node < 0)
444                         area->pages[i] = alloc_page(gfp_mask);
445                 else
446                         area->pages[i] = alloc_pages_node(node, gfp_mask, 0);
447                 if (unlikely(!area->pages[i])) {
448                         /* Successfully allocated i pages, free them in __vunmap() */
449                         area->nr_pages = i;
450                         goto fail;
451                 }
452         }
453
454         if (map_vm_area(area, prot, &pages))
455                 goto fail;
456         return area->addr;
457
458 fail:
459         vfree(area->addr);
460         return NULL;
461 }
462
463 void *__vmalloc_area(struct vm_struct *area, gfp_t gfp_mask, pgprot_t prot)
464 {
465         return __vmalloc_area_node(area, gfp_mask, prot, -1);
466 }
467
468 /**
469  *      __vmalloc_node  -  allocate virtually contiguous memory
470  *
471  *      @size:          allocation size
472  *      @gfp_mask:      flags for the page level allocator
473  *      @prot:          protection mask for the allocated pages
474  *      @node:          node to use for allocation or -1
475  *
476  *      Allocate enough pages to cover @size from the page level
477  *      allocator with @gfp_mask flags.  Map them into contiguous
478  *      kernel virtual space, using a pagetable protection of @prot.
479  */
480 void *__vmalloc_node(unsigned long size, gfp_t gfp_mask, pgprot_t prot,
481                         int node)
482 {
483         struct vm_struct *area;
484
485         size = PAGE_ALIGN(size);
486         if (!size || (size >> PAGE_SHIFT) > num_physpages)
487                 return NULL;
488
489         area = get_vm_area_node(size, VM_ALLOC, node);
490         if (!area)
491                 return NULL;
492
493         return __vmalloc_area_node(area, gfp_mask, prot, node);
494 }
495 EXPORT_SYMBOL(__vmalloc_node);
496
497 void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot)
498 {
499         return __vmalloc_node(size, gfp_mask, prot, -1);
500 }
501 EXPORT_SYMBOL(__vmalloc);
502
503 /**
504  *      vmalloc  -  allocate virtually contiguous memory
505  *
506  *      @size:          allocation size
507  *
508  *      Allocate enough pages to cover @size from the page level
509  *      allocator and map them into contiguous kernel virtual space.
510  *
511  *      For tight cotrol over page level allocator and protection flags
512  *      use __vmalloc() instead.
513  */
514 void *vmalloc(unsigned long size)
515 {
516         return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL);
517 }
518 EXPORT_SYMBOL(vmalloc);
519
520 /**
521  *      vmalloc_user  -  allocate virtually contiguous memory which has
522  *                         been zeroed so it can be mapped to userspace without
523  *                         leaking data.
524  *
525  *      @size:          allocation size
526  */
527 void *vmalloc_user(unsigned long size)
528 {
529         struct vm_struct *area;
530         void *ret;
531
532         ret = __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO, PAGE_KERNEL);
533         write_lock(&vmlist_lock);
534         area = __find_vm_area(ret);
535         area->flags |= VM_USERMAP;
536         write_unlock(&vmlist_lock);
537
538         return ret;
539 }
540 EXPORT_SYMBOL(vmalloc_user);
541
542 /**
543  *      vmalloc_node  -  allocate memory on a specific node
544  *
545  *      @size:          allocation size
546  *      @node:          numa node
547  *
548  *      Allocate enough pages to cover @size from the page level
549  *      allocator and map them into contiguous kernel virtual space.
550  *
551  *      For tight cotrol over page level allocator and protection flags
552  *      use __vmalloc() instead.
553  */
554 void *vmalloc_node(unsigned long size, int node)
555 {
556         return __vmalloc_node(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL, node);
557 }
558 EXPORT_SYMBOL(vmalloc_node);
559
560 #ifndef PAGE_KERNEL_EXEC
561 # define PAGE_KERNEL_EXEC PAGE_KERNEL
562 #endif
563
564 /**
565  *      vmalloc_exec  -  allocate virtually contiguous, executable memory
566  *
567  *      @size:          allocation size
568  *
569  *      Kernel-internal function to allocate enough pages to cover @size
570  *      the page level allocator and map them into contiguous and
571  *      executable kernel virtual space.
572  *
573  *      For tight cotrol over page level allocator and protection flags
574  *      use __vmalloc() instead.
575  */
576
577 void *vmalloc_exec(unsigned long size)
578 {
579         return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL_EXEC);
580 }
581
582 /**
583  *      vmalloc_32  -  allocate virtually contiguous memory (32bit addressable)
584  *
585  *      @size:          allocation size
586  *
587  *      Allocate enough 32bit PA addressable pages to cover @size from the
588  *      page level allocator and map them into contiguous kernel virtual space.
589  */
590 void *vmalloc_32(unsigned long size)
591 {
592         return __vmalloc(size, GFP_KERNEL, PAGE_KERNEL);
593 }
594 EXPORT_SYMBOL(vmalloc_32);
595
596 /**
597  *      vmalloc_32_user  -  allocate virtually contiguous memory (32bit
598  *                            addressable) which is zeroed so it can be
599  *                            mapped to userspace without leaking data.
600  *
601  *      @size:          allocation size
602  */
603 void *vmalloc_32_user(unsigned long size)
604 {
605         struct vm_struct *area;
606         void *ret;
607
608         ret = __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
609         write_lock(&vmlist_lock);
610         area = __find_vm_area(ret);
611         area->flags |= VM_USERMAP;
612         write_unlock(&vmlist_lock);
613
614         return ret;
615 }
616 EXPORT_SYMBOL(vmalloc_32_user);
617
618 long vread(char *buf, char *addr, unsigned long count)
619 {
620         struct vm_struct *tmp;
621         char *vaddr, *buf_start = buf;
622         unsigned long n;
623
624         /* Don't allow overflow */
625         if ((unsigned long) addr + count < count)
626                 count = -(unsigned long) addr;
627
628         read_lock(&vmlist_lock);
629         for (tmp = vmlist; tmp; tmp = tmp->next) {
630                 vaddr = (char *) tmp->addr;
631                 if (addr >= vaddr + tmp->size - PAGE_SIZE)
632                         continue;
633                 while (addr < vaddr) {
634                         if (count == 0)
635                                 goto finished;
636                         *buf = '\0';
637                         buf++;
638                         addr++;
639                         count--;
640                 }
641                 n = vaddr + tmp->size - PAGE_SIZE - addr;
642                 do {
643                         if (count == 0)
644                                 goto finished;
645                         *buf = *addr;
646                         buf++;
647                         addr++;
648                         count--;
649                 } while (--n > 0);
650         }
651 finished:
652         read_unlock(&vmlist_lock);
653         return buf - buf_start;
654 }
655
656 long vwrite(char *buf, char *addr, unsigned long count)
657 {
658         struct vm_struct *tmp;
659         char *vaddr, *buf_start = buf;
660         unsigned long n;
661
662         /* Don't allow overflow */
663         if ((unsigned long) addr + count < count)
664                 count = -(unsigned long) addr;
665
666         read_lock(&vmlist_lock);
667         for (tmp = vmlist; tmp; tmp = tmp->next) {
668                 vaddr = (char *) tmp->addr;
669                 if (addr >= vaddr + tmp->size - PAGE_SIZE)
670                         continue;
671                 while (addr < vaddr) {
672                         if (count == 0)
673                                 goto finished;
674                         buf++;
675                         addr++;
676                         count--;
677                 }
678                 n = vaddr + tmp->size - PAGE_SIZE - addr;
679                 do {
680                         if (count == 0)
681                                 goto finished;
682                         *addr = *buf;
683                         buf++;
684                         addr++;
685                         count--;
686                 } while (--n > 0);
687         }
688 finished:
689         read_unlock(&vmlist_lock);
690         return buf - buf_start;
691 }
692
693 /**
694  *      remap_vmalloc_range  -  map vmalloc pages to userspace
695  *
696  *      @vma:           vma to cover (map full range of vma)
697  *      @addr:          vmalloc memory
698  *      @pgoff:         number of pages into addr before first page to map
699  *      @returns:       0 for success, -Exxx on failure
700  *
701  *      This function checks that addr is a valid vmalloc'ed area, and
702  *      that it is big enough to cover the vma. Will return failure if
703  *      that criteria isn't met.
704  *
705  *      Similar to remap_pfn_range (see mm/memory.c)
706  */
707 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
708                                                 unsigned long pgoff)
709 {
710         struct vm_struct *area;
711         unsigned long uaddr = vma->vm_start;
712         unsigned long usize = vma->vm_end - vma->vm_start;
713         int ret;
714
715         if ((PAGE_SIZE-1) & (unsigned long)addr)
716                 return -EINVAL;
717
718         read_lock(&vmlist_lock);
719         area = __find_vm_area(addr);
720         if (!area)
721                 goto out_einval_locked;
722
723         if (!(area->flags & VM_USERMAP))
724                 goto out_einval_locked;
725
726         if (usize + (pgoff << PAGE_SHIFT) > area->size - PAGE_SIZE)
727                 goto out_einval_locked;
728         read_unlock(&vmlist_lock);
729
730         addr += pgoff << PAGE_SHIFT;
731         do {
732                 struct page *page = vmalloc_to_page(addr);
733                 ret = vm_insert_page(vma, uaddr, page);
734                 if (ret)
735                         return ret;
736
737                 uaddr += PAGE_SIZE;
738                 addr += PAGE_SIZE;
739                 usize -= PAGE_SIZE;
740         } while (usize > 0);
741
742         /* Prevent "things" like memory migration? VM_flags need a cleanup... */
743         vma->vm_flags |= VM_RESERVED;
744
745         return ret;
746
747 out_einval_locked:
748         read_unlock(&vmlist_lock);
749         return -EINVAL;
750 }
751 EXPORT_SYMBOL(remap_vmalloc_range);
752