V4L/DVB (4121): Update cardlist documentation
[linux-2.6] / 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         if (deallocate_pages) {
334                 int i;
335
336                 for (i = 0; i < area->nr_pages; i++) {
337                         BUG_ON(!area->pages[i]);
338                         __free_page(area->pages[i]);
339                 }
340
341                 if (area->nr_pages > PAGE_SIZE/sizeof(struct page *))
342                         vfree(area->pages);
343                 else
344                         kfree(area->pages);
345         }
346
347         kfree(area);
348         return;
349 }
350
351 /**
352  *      vfree  -  release memory allocated by vmalloc()
353  *
354  *      @addr:          memory base address
355  *
356  *      Free the virtually contiguous memory area starting at @addr, as
357  *      obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is
358  *      NULL, no operation is performed.
359  *
360  *      Must not be called in interrupt context.
361  */
362 void vfree(void *addr)
363 {
364         BUG_ON(in_interrupt());
365         __vunmap(addr, 1);
366 }
367 EXPORT_SYMBOL(vfree);
368
369 /**
370  *      vunmap  -  release virtual mapping obtained by vmap()
371  *
372  *      @addr:          memory base address
373  *
374  *      Free the virtually contiguous memory area starting at @addr,
375  *      which was created from the page array passed to vmap().
376  *
377  *      Must not be called in interrupt context.
378  */
379 void vunmap(void *addr)
380 {
381         BUG_ON(in_interrupt());
382         __vunmap(addr, 0);
383 }
384 EXPORT_SYMBOL(vunmap);
385
386 /**
387  *      vmap  -  map an array of pages into virtually contiguous space
388  *
389  *      @pages:         array of page pointers
390  *      @count:         number of pages to map
391  *      @flags:         vm_area->flags
392  *      @prot:          page protection for the mapping
393  *
394  *      Maps @count pages from @pages into contiguous kernel virtual
395  *      space.
396  */
397 void *vmap(struct page **pages, unsigned int count,
398                 unsigned long flags, pgprot_t prot)
399 {
400         struct vm_struct *area;
401
402         if (count > num_physpages)
403                 return NULL;
404
405         area = get_vm_area((count << PAGE_SHIFT), flags);
406         if (!area)
407                 return NULL;
408         if (map_vm_area(area, prot, &pages)) {
409                 vunmap(area->addr);
410                 return NULL;
411         }
412
413         return area->addr;
414 }
415 EXPORT_SYMBOL(vmap);
416
417 void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
418                                 pgprot_t prot, int node)
419 {
420         struct page **pages;
421         unsigned int nr_pages, array_size, i;
422
423         nr_pages = (area->size - PAGE_SIZE) >> PAGE_SHIFT;
424         array_size = (nr_pages * sizeof(struct page *));
425
426         area->nr_pages = nr_pages;
427         /* Please note that the recursion is strictly bounded. */
428         if (array_size > PAGE_SIZE)
429                 pages = __vmalloc_node(array_size, gfp_mask, PAGE_KERNEL, node);
430         else
431                 pages = kmalloc_node(array_size, (gfp_mask & ~__GFP_HIGHMEM), node);
432         area->pages = pages;
433         if (!area->pages) {
434                 remove_vm_area(area->addr);
435                 kfree(area);
436                 return NULL;
437         }
438         memset(area->pages, 0, array_size);
439
440         for (i = 0; i < area->nr_pages; i++) {
441                 if (node < 0)
442                         area->pages[i] = alloc_page(gfp_mask);
443                 else
444                         area->pages[i] = alloc_pages_node(node, gfp_mask, 0);
445                 if (unlikely(!area->pages[i])) {
446                         /* Successfully allocated i pages, free them in __vunmap() */
447                         area->nr_pages = i;
448                         goto fail;
449                 }
450         }
451
452         if (map_vm_area(area, prot, &pages))
453                 goto fail;
454         return area->addr;
455
456 fail:
457         vfree(area->addr);
458         return NULL;
459 }
460
461 void *__vmalloc_area(struct vm_struct *area, gfp_t gfp_mask, pgprot_t prot)
462 {
463         return __vmalloc_area_node(area, gfp_mask, prot, -1);
464 }
465
466 /**
467  *      __vmalloc_node  -  allocate virtually contiguous memory
468  *
469  *      @size:          allocation size
470  *      @gfp_mask:      flags for the page level allocator
471  *      @prot:          protection mask for the allocated pages
472  *      @node:          node to use for allocation or -1
473  *
474  *      Allocate enough pages to cover @size from the page level
475  *      allocator with @gfp_mask flags.  Map them into contiguous
476  *      kernel virtual space, using a pagetable protection of @prot.
477  */
478 void *__vmalloc_node(unsigned long size, gfp_t gfp_mask, pgprot_t prot,
479                         int node)
480 {
481         struct vm_struct *area;
482
483         size = PAGE_ALIGN(size);
484         if (!size || (size >> PAGE_SHIFT) > num_physpages)
485                 return NULL;
486
487         area = get_vm_area_node(size, VM_ALLOC, node);
488         if (!area)
489                 return NULL;
490
491         return __vmalloc_area_node(area, gfp_mask, prot, node);
492 }
493 EXPORT_SYMBOL(__vmalloc_node);
494
495 void *__vmalloc(unsigned long size, gfp_t gfp_mask, pgprot_t prot)
496 {
497         return __vmalloc_node(size, gfp_mask, prot, -1);
498 }
499 EXPORT_SYMBOL(__vmalloc);
500
501 /**
502  *      vmalloc  -  allocate virtually contiguous memory
503  *
504  *      @size:          allocation size
505  *
506  *      Allocate enough pages to cover @size from the page level
507  *      allocator and map them into contiguous kernel virtual space.
508  *
509  *      For tight cotrol over page level allocator and protection flags
510  *      use __vmalloc() instead.
511  */
512 void *vmalloc(unsigned long size)
513 {
514         return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL);
515 }
516 EXPORT_SYMBOL(vmalloc);
517
518 /**
519  *      vmalloc_user  -  allocate virtually contiguous memory which has
520  *                         been zeroed so it can be mapped to userspace without
521  *                         leaking data.
522  *
523  *      @size:          allocation size
524  */
525 void *vmalloc_user(unsigned long size)
526 {
527         struct vm_struct *area;
528         void *ret;
529
530         ret = __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM | __GFP_ZERO, PAGE_KERNEL);
531         write_lock(&vmlist_lock);
532         area = __find_vm_area(ret);
533         area->flags |= VM_USERMAP;
534         write_unlock(&vmlist_lock);
535
536         return ret;
537 }
538 EXPORT_SYMBOL(vmalloc_user);
539
540 /**
541  *      vmalloc_node  -  allocate memory on a specific node
542  *
543  *      @size:          allocation size
544  *      @node:          numa node
545  *
546  *      Allocate enough pages to cover @size from the page level
547  *      allocator and map them into contiguous kernel virtual space.
548  *
549  *      For tight cotrol over page level allocator and protection flags
550  *      use __vmalloc() instead.
551  */
552 void *vmalloc_node(unsigned long size, int node)
553 {
554         return __vmalloc_node(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL, node);
555 }
556 EXPORT_SYMBOL(vmalloc_node);
557
558 #ifndef PAGE_KERNEL_EXEC
559 # define PAGE_KERNEL_EXEC PAGE_KERNEL
560 #endif
561
562 /**
563  *      vmalloc_exec  -  allocate virtually contiguous, executable memory
564  *
565  *      @size:          allocation size
566  *
567  *      Kernel-internal function to allocate enough pages to cover @size
568  *      the page level allocator and map them into contiguous and
569  *      executable kernel virtual space.
570  *
571  *      For tight cotrol over page level allocator and protection flags
572  *      use __vmalloc() instead.
573  */
574
575 void *vmalloc_exec(unsigned long size)
576 {
577         return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL_EXEC);
578 }
579
580 /**
581  *      vmalloc_32  -  allocate virtually contiguous memory (32bit addressable)
582  *
583  *      @size:          allocation size
584  *
585  *      Allocate enough 32bit PA addressable pages to cover @size from the
586  *      page level allocator and map them into contiguous kernel virtual space.
587  */
588 void *vmalloc_32(unsigned long size)
589 {
590         return __vmalloc(size, GFP_KERNEL, PAGE_KERNEL);
591 }
592 EXPORT_SYMBOL(vmalloc_32);
593
594 /**
595  *      vmalloc_32_user  -  allocate virtually contiguous memory (32bit
596  *                            addressable) which is zeroed so it can be
597  *                            mapped to userspace without leaking data.
598  *
599  *      @size:          allocation size
600  */
601 void *vmalloc_32_user(unsigned long size)
602 {
603         struct vm_struct *area;
604         void *ret;
605
606         ret = __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
607         write_lock(&vmlist_lock);
608         area = __find_vm_area(ret);
609         area->flags |= VM_USERMAP;
610         write_unlock(&vmlist_lock);
611
612         return ret;
613 }
614 EXPORT_SYMBOL(vmalloc_32_user);
615
616 long vread(char *buf, char *addr, unsigned long count)
617 {
618         struct vm_struct *tmp;
619         char *vaddr, *buf_start = buf;
620         unsigned long n;
621
622         /* Don't allow overflow */
623         if ((unsigned long) addr + count < count)
624                 count = -(unsigned long) addr;
625
626         read_lock(&vmlist_lock);
627         for (tmp = vmlist; tmp; tmp = tmp->next) {
628                 vaddr = (char *) tmp->addr;
629                 if (addr >= vaddr + tmp->size - PAGE_SIZE)
630                         continue;
631                 while (addr < vaddr) {
632                         if (count == 0)
633                                 goto finished;
634                         *buf = '\0';
635                         buf++;
636                         addr++;
637                         count--;
638                 }
639                 n = vaddr + tmp->size - PAGE_SIZE - addr;
640                 do {
641                         if (count == 0)
642                                 goto finished;
643                         *buf = *addr;
644                         buf++;
645                         addr++;
646                         count--;
647                 } while (--n > 0);
648         }
649 finished:
650         read_unlock(&vmlist_lock);
651         return buf - buf_start;
652 }
653
654 long vwrite(char *buf, char *addr, unsigned long count)
655 {
656         struct vm_struct *tmp;
657         char *vaddr, *buf_start = buf;
658         unsigned long n;
659
660         /* Don't allow overflow */
661         if ((unsigned long) addr + count < count)
662                 count = -(unsigned long) addr;
663
664         read_lock(&vmlist_lock);
665         for (tmp = vmlist; tmp; tmp = tmp->next) {
666                 vaddr = (char *) tmp->addr;
667                 if (addr >= vaddr + tmp->size - PAGE_SIZE)
668                         continue;
669                 while (addr < vaddr) {
670                         if (count == 0)
671                                 goto finished;
672                         buf++;
673                         addr++;
674                         count--;
675                 }
676                 n = vaddr + tmp->size - PAGE_SIZE - addr;
677                 do {
678                         if (count == 0)
679                                 goto finished;
680                         *addr = *buf;
681                         buf++;
682                         addr++;
683                         count--;
684                 } while (--n > 0);
685         }
686 finished:
687         read_unlock(&vmlist_lock);
688         return buf - buf_start;
689 }
690
691 /**
692  *      remap_vmalloc_range  -  map vmalloc pages to userspace
693  *
694  *      @vma:           vma to cover (map full range of vma)
695  *      @addr:          vmalloc memory
696  *      @pgoff:         number of pages into addr before first page to map
697  *      @returns:       0 for success, -Exxx on failure
698  *
699  *      This function checks that addr is a valid vmalloc'ed area, and
700  *      that it is big enough to cover the vma. Will return failure if
701  *      that criteria isn't met.
702  *
703  *      Similar to remap_pfn_range (see mm/memory.c)
704  */
705 int remap_vmalloc_range(struct vm_area_struct *vma, void *addr,
706                                                 unsigned long pgoff)
707 {
708         struct vm_struct *area;
709         unsigned long uaddr = vma->vm_start;
710         unsigned long usize = vma->vm_end - vma->vm_start;
711         int ret;
712
713         if ((PAGE_SIZE-1) & (unsigned long)addr)
714                 return -EINVAL;
715
716         read_lock(&vmlist_lock);
717         area = __find_vm_area(addr);
718         if (!area)
719                 goto out_einval_locked;
720
721         if (!(area->flags & VM_USERMAP))
722                 goto out_einval_locked;
723
724         if (usize + (pgoff << PAGE_SHIFT) > area->size - PAGE_SIZE)
725                 goto out_einval_locked;
726         read_unlock(&vmlist_lock);
727
728         addr += pgoff << PAGE_SHIFT;
729         do {
730                 struct page *page = vmalloc_to_page(addr);
731                 ret = vm_insert_page(vma, uaddr, page);
732                 if (ret)
733                         return ret;
734
735                 uaddr += PAGE_SIZE;
736                 addr += PAGE_SIZE;
737                 usize -= PAGE_SIZE;
738         } while (usize > 0);
739
740         /* Prevent "things" like memory migration? VM_flags need a cleanup... */
741         vma->vm_flags |= VM_RESERVED;
742
743         return ret;
744
745 out_einval_locked:
746         read_unlock(&vmlist_lock);
747         return -EINVAL;
748 }
749 EXPORT_SYMBOL(remap_vmalloc_range);
750