Previous Up Next

Appendix G  Non-Contiguous Memory Allocation

G.1  Allocating A Non-Contiguous Area

G.1.1  Function: vmalloc

Source: include/linux/vmalloc.h

The call graph for this function is shown in Figure 7.2. The following macros only by their GFP_ flags (See Section 6.4). The size parameter is page aligned by __vmalloc()(See Section G.1.2).

 37 static inline void * vmalloc (unsigned long size)
 38 {
 39     return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL);
 40 }
 46 static inline void * vmalloc_dma (unsigned long size)
 47 {
 48     return __vmalloc(size, GFP_KERNEL|GFP_DMA, PAGE_KERNEL);
 49 }
 55 static inline void * vmalloc_32(unsigned long size)
 56 {
 57     return __vmalloc(size, GFP_KERNEL, PAGE_KERNEL);
 58 }
37The flags indicate that to use either ZONE_NORMAL or ZONE_HIGHMEM as necessary
46The flag indicates to only allocate from ZONE_DMA
55Only physical pages from ZONE_NORMAL will be allocated

G.1.2  Function: __vmalloc

Source: mm/vmalloc.c

This function has three tasks. It page aligns the size request, asks get_vm_area() to find an area for the request and uses vmalloc_area_pages() to allocate the PTEs for the pages.

261 void * __vmalloc (unsigned long size, int gfp_mask, pgprot_t prot)
262 {
263     void * addr;
264     struct vm_struct *area;
266     size = PAGE_ALIGN(size);
267     if (!size || (size >> PAGE_SHIFT) > num_physpages)
268         return NULL;
269     area = get_vm_area(size, VM_ALLOC);
270     if (!area)
271         return NULL;
272     addr = area->addr;
273     if (__vmalloc_area_pages(VMALLOC_VMADDR(addr), size, gfp_mask,
274                              prot, NULL)) {
275         vfree(addr);
276         return NULL;
277     }
278     return addr;
279 }
261The parameters are the size to allocate, the GFP_ flags to use for allocation and what protection to give the PTE
266Align the size to a page size
267Sanity check. Make sure the size is not 0 and that the size requested is not larger than the number of physical pages has been requested
269Find an area of virtual address space to store the allocation with get_vm_area() (See Section G.1.3)
272The addr field has been filled by get_vm_area()
273Allocate the PTE entries needed for the allocation with __vmalloc_area_pages() (See Section G.1.5). If it fails, a non-zero value -ENOMEM is returned
275-276If the allocation fails, free any PTEs, pages and descriptions of the area
278Return the address of the allocated area

G.1.3  Function: get_vm_area

Source: mm/vmalloc.c

To allocate an area for the vm_struct, the slab allocator is asked to provide the necessary memory via kmalloc(). It then searches the vm_struct list linearaly looking for a region large enough to satisfy a request, including a page pad at the end of the area.

195 struct vm_struct * get_vm_area(unsigned long size, 
                                   unsigned long flags)
196 {
197     unsigned long addr, next;
198     struct vm_struct **p, *tmp, *area;
200     area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL);
201     if (!area)
202         return NULL;
204     size += PAGE_SIZE;
205     if(!size) {
206         kfree (area);
207         return NULL;
208     }
210     addr = VMALLOC_START;
211     write_lock(&vmlist_lock);
212     for (p = &vmlist; (tmp = *p) ; p = &tmp->next) {
213         if ((size + addr) < addr)
214             goto out;
215         if (size + addr <= (unsigned long) tmp->addr)
216             break;
217         next = tmp->size + (unsigned long) tmp->addr;
218         if (next > addr)
219             addr = next;
220         if (addr > VMALLOC_END-size)
221             goto out;
222     }
223     area->flags = flags;
224     area->addr = (void *)addr;
225     area->size = size;
226     area->next = *p;
227     *p = area;
228     write_unlock(&vmlist_lock);
229     return area;
231 out:
232     write_unlock(&vmlist_lock);
233     kfree(area);
234     return NULL;
235 }
195The parameters is the size of the requested region which should be a multiple of the page size and the area flags, either VM_ALLOC or VM_IOREMAP
200-202Allocate space for the vm_struct description struct
204Pad the request so there is a page gap between areas. This is to guard against overwrites
205-206This is to ensure the size is not 0 after the padding due to an overflow. If something does go wrong, free the area just allocated and return NULL
210Start the search at the beginning of the vmalloc address space
211Lock the list
212-222Walk through the list searching for an area large enough for the request
213-214Check to make sure the end of the addressable range has not been reached
215-216If the requested area would fit between the current address and the next area, the search is complete
217Make sure the address would not go over the end of the vmalloc address space
223-225Copy in the area information
226-227Link the new area into the list
228-229Unlock the list and return
231This label is reached if the request could not be satisfied
232Unlock the list
233-234Free the memory used for the area descriptor and return

G.1.4  Function: vmalloc_area_pages

Source: mm/vmalloc.c

This is just a wrapper around __vmalloc_area_pages(). This function exists for compatibility with older kernels. The name change was made to reflect that the new function __vmalloc_area_pages() is able to take an array of pages to use for insertion into the pagetables.

189 int vmalloc_area_pages(unsigned long address, unsigned long size,
190                        int gfp_mask, pgprot_t prot)
191 {
192         return __vmalloc_area_pages(address, size, gfp_mask, prot, NULL);
193 }
192Call __vmalloc_area_pages() with the same parameters. The pages array is passed as NULL as the pages will be allocated as necessary

G.1.5  Function: __vmalloc_area_pages

Source: mm/vmalloc.c

This is the beginning of a standard page table walk function. This top level function will step through all PGDs within an address range. For each PGD, it will call pmd_alloc() to allocate a PMD directory and call alloc_area_pmd() for the directory.

155 static inline int __vmalloc_area_pages (unsigned long address,
156                                         unsigned long size,
157                                         int gfp_mask,
158                                         pgprot_t prot,
159                                         struct page ***pages)
160 {
161     pgd_t * dir;
162     unsigned long end = address + size;
163     int ret;
165     dir = pgd_offset_k(address);
166     spin_lock(&init_mm.page_table_lock);
167     do {
168         pmd_t *pmd;
170         pmd = pmd_alloc(&init_mm, dir, address);
171         ret = -ENOMEM;
172         if (!pmd)
173             break;
175         ret = -ENOMEM;
176         if (alloc_area_pmd(pmd, address, end - address, 
                       gfp_mask, prot, pages))
177             break;
179         address = (address + PGDIR_SIZE) & PGDIR_MASK;
180         dir++;
182         ret = 0;
183     } while (address && (address < end));
184     spin_unlock(&init_mm.page_table_lock);
185     flush_cache_all();
186     return ret;
187 }
155The parameters are;
address is the starting address to allocate PMDs for
size is the size of the region
gfp_mask is the GFP_ flags for alloc_pages() (See Section F.1.1)
prot is the protection to give the PTE entry
pages is an array of pages to use for insertion instead of having alloc_area_pte() allocate them one at a time. Only the vmap() interface passes in an array
162The end address is the starting address plus the size
165Get the PGD entry for the starting address
166Lock the kernel reference page table
167-183For every PGD within this address range, allocate a PMD directory and call alloc_area_pmd() (See Section G.1.6)
170Allocate a PMD directory
176Call alloc_area_pmd() (See Section G.1.6) which will allocate a PTE for each PTE slot in the PMD
179address becomes the base address of the next PGD entry
180Move dir to the next PGD entry
184Release the lock to the kernel page table
185flush_cache_all() will flush all CPU caches. This is necessary because the kernel page tables have changed
186Return success

G.1.6  Function: alloc_area_pmd

Source: mm/vmalloc.c

This is the second stage of the standard page table walk to allocate PTE entries for an address range. For every PMD within a given address range on a PGD, pte_alloc() will creates a PTE directory and then alloc_area_pte() will be called to allocate the physical pages

132 static inline int alloc_area_pmd(pmd_t * pmd, unsigned long address,
133                         unsigned long size, int gfp_mask,
134                         pgprot_t prot, struct page ***pages)
135 {
136     unsigned long end;
138     address &= ~PGDIR_MASK;
139     end = address + size;
140     if (end > PGDIR_SIZE)
141         end = PGDIR_SIZE;
142     do {
143         pte_t * pte = pte_alloc(&init_mm, pmd, address);
144         if (!pte)
145             return -ENOMEM;
146         if (alloc_area_pte(pte, address, end - address, 
147                    gfp_mask, prot, pages))
148             return -ENOMEM;
149         address = (address + PMD_SIZE) & PMD_MASK;
150         pmd++;
151     } while (address < end);
152     return 0;
152 }
132The parameters are;
pmd is the PMD that needs the allocations
address is the starting address to start from
size is the size of the region within the PMD to allocate for
gfp_mask is the GFP_ flags for alloc_pages() (See Section F.1.1)
prot is the protection to give the PTE entry
pages is an optional array of pages to use instead of allocating each page individually
138Align the starting address to the PGD
139-141Calculate end to be the end of the allocation or the end of the PGD, whichever occurs first
142-151For every PMD within the given address range, allocate a PTE directory and call alloc_area_pte()(See Section G.1.7)
143Allocate the PTE directory
146-147Call alloc_area_pte() which will allocate the physical pages if an array of pages is not already supplied with pages
149address becomes the base address of the next PMD entry
150Move pmd to the next PMD entry
152Return success

G.1.7  Function: alloc_area_pte

Source: mm/vmalloc.c

This is the last stage of the page table walk. For every PTE in the given PTE directory and address range, a page will be allocated and associated with the PTE.

 95 static inline int alloc_area_pte (pte_t * pte, unsigned long address,
 96                         unsigned long size, int gfp_mask,
 97                         pgprot_t prot, struct page ***pages)
 98 {
 99     unsigned long end;
101     address &= ~PMD_MASK;
102     end = address + size;
103     if (end > PMD_SIZE)
104         end = PMD_SIZE;
105     do {
106         struct page * page;
108         if (!pages) {
109             spin_unlock(&init_mm.page_table_lock);
110             page = alloc_page(gfp_mask);
111             spin_lock(&init_mm.page_table_lock);
112         } else {
113             page = (**pages);
114             (*pages)++;
116             /* Add a reference to the page so we can free later */
117             if (page)
118                 atomic_inc(&page->count);
120         }
121         if (!pte_none(*pte))
122             printk(KERN_ERR "alloc_area_pte: page already exists\n");
123         if (!page)
124             return -ENOMEM;
125         set_pte(pte, mk_pte(page, prot));
126         address += PAGE_SIZE;
127         pte++;
128     } while (address < end);
129     return 0;
130 }
101Align the address to a PMD directory
103-104The end address is the end of the request or the end of the directory, whichever occurs first
105-128Loop through every PTE in this page. If a pages array is supplied, use pages from it to populate the table, otherwise allocate each one individually
108-111If an array of pages is not supplied, unlock the kernel reference pagetable, allocate a page with alloc_page() and reacquire the spinlock
112-120Else, take one page from the array and increment it's usage count as it is about to be inserted into the reference page table
121-122If the PTE is already in use, it means that the areas in the vmalloc region are overlapping somehow
123-124Return failure if physical pages are not available
125Set the page with the desired protection bits (prot) into the PTE
126address becomes the address of the next PTE
127Move to the next PTE
129Return success

G.1.8  Function: vmap

Source: mm/vmalloc.c

This function allows a caller-supplied array of pages to be inserted into the vmalloc address space. This is unused in 2.4.22 and I suspect it is an accidental backport from 2.6.x where it is used by the sound subsystem core.

281 void * vmap(struct page **pages, int count,
282             unsigned long flags, pgprot_t prot)
283 {
284     void * addr;
285     struct vm_struct *area;
286     unsigned long size = count << PAGE_SHIFT;
288     if (!size || size > (max_mapnr << PAGE_SHIFT))
289         return NULL;
290     area = get_vm_area(size, flags);
291     if (!area) {
292         return NULL;
293     }
294     addr = area->addr;
295     if (__vmalloc_area_pages(VMALLOC_VMADDR(addr), size, 0,
296                              prot, &pages)) {
297         vfree(addr);
298         return NULL;
299     }
300     return addr;
301 }
281The parameters are;
pages is the caller-supplied array of pages to insert
count is the number of pages in the array
flags is the flags to use for the vm_struct
prot is the protection bits to set the PTE with
286Calculate the size in bytes of the region to create based on the size of the array
288-289Make sure the size of the region does not exceed limits
290-293Use get_vm_area() to find a region large enough for the mapping. If one is not found, return NULL
294Get the virtual address of the area
295Insert the array into the pagetable with __vmalloc_area_pages() (See Section G.1.4)
297If the insertion fails, free the region and return NULL
298Return the virtual address of the newly mapped region

G.2  Freeing A Non-Contiguous Area

G.2.1  Function: vfree

Source: mm/vmalloc.c

The call graph for this function is shown in Figure 7.4. This is the top level function responsible for freeing a non-contiguous area of memory. It performs basic sanity checks before finding the vm_struct for the requested addr. Once found, it calls vmfree_area_pages().

237 void vfree(void * addr)
238 {
239     struct vm_struct **p, *tmp;
241     if (!addr)
242         return;
243     if ((PAGE_SIZE-1) & (unsigned long) addr) {
244         printk(KERN_ERR 
               "Trying to vfree() bad address (%p)\n", addr);
245         return;
246     }
247     write_lock(&vmlist_lock);
248     for (p = &vmlist ; (tmp = *p) ; p = &tmp->next) {
249         if (tmp->addr == addr) {
250             *p = tmp->next;
251             vmfree_area_pages(VMALLOC_VMADDR(tmp->addr), 
252             write_unlock(&vmlist_lock);
253             kfree(tmp);
254             return;
255         }
256     }
257     write_unlock(&vmlist_lock);
258     printk(KERN_ERR 
           "Trying to vfree() nonexistent vm area (%p)\n", addr);
259 }
237The parameter is the address returned by get_vm_area() (See Section G.1.3) to either vmalloc() or ioremap()
241-243Ignore NULL addresses
243-246This checks the address is page aligned and is a reasonable quick guess to see if the area is valid or not
247Acquire a write lock to the vmlist
248Cycle through the vmlist looking for the correct vm_struct for addr
249If this it the correct address then ...
250Remove this area from the vmlist linked list
251Free all pages associated with the address range
252Release the vmlist lock
253Free the memory used for the vm_struct and return
257-258The vm_struct was not found. Release the lock and print a message about the failed free

G.2.2  Function: vmfree_area_pages

Source: mm/vmalloc.c

This is the first stage of the page table walk to free all pages and PTEs associated with an address range. It is responsible for stepping through the relevant PGDs and for flushing the TLB.

 80 void vmfree_area_pages(unsigned long address, unsigned long size)
 81 {
 82     pgd_t * dir;
 83     unsigned long end = address + size;
 85     dir = pgd_offset_k(address);
 86     flush_cache_all();
 87     do {
 88         free_area_pmd(dir, address, end - address);
 89         address = (address + PGDIR_SIZE) & PGDIR_MASK;
 90         dir++;
 91     } while (address && (address < end));
 92     flush_tlb_all();
 93 }
80The parameters are the starting address and the size of the region
82The address space end is the starting address plus its size
85Get the first PGD for the address range
86Flush the cache CPU so cache hits will not occur on pages that are to be deleted. This is a null operation on many architectures including the x86
87Call free_area_pmd()(See Section G.2.3) to perform the second stage of the page table walk
89address becomes the starting address of the next PGD
90Move to the next PGD
92Flush the TLB as the page tables have now changed

G.2.3  Function: free_area_pmd

Source: mm/vmalloc.c

This is the second stage of the page table walk. For every PMD in this directory, call free_area_pte() to free up the pages and PTEs.

 56 static inline void free_area_pmd(pgd_t * dir, 
                     unsigned long address,
                     unsigned long size)
 57 {
 58     pmd_t * pmd;
 59     unsigned long end;
 61     if (pgd_none(*dir))
 62         return;
 63     if (pgd_bad(*dir)) {
 64         pgd_ERROR(*dir);
 65         pgd_clear(dir);
 66         return;
 67     }
 68     pmd = pmd_offset(dir, address);
 69     address &= ~PGDIR_MASK;
 70     end = address + size;
 71     if (end > PGDIR_SIZE)
 72         end = PGDIR_SIZE;
 73     do {
 74         free_area_pte(pmd, address, end - address);
 75         address = (address + PMD_SIZE) & PMD_MASK;
 76         pmd++;
 77     } while (address < end);
 78 }
56The parameters are the PGD been stepped through, the starting address and the length of the region
61-62If there is no PGD, return. This can occur after vfree() (See Section G.2.1) is called during a failed allocation
63-67A PGD can be bad if the entry is not present, it is marked read-only or it is marked accessed or dirty
68Get the first PMD for the address range
69Make the address PGD aligned
70-72end is either the end of the space to free or the end of this PGD, whichever is first
73-77For every PMD, call free_area_pte() (See Section G.2.4) to free the PTE entries
75address is the base address of the next PMD
76Move to the next PMD

G.2.4  Function: free_area_pte

Source: mm/vmalloc.c

This is the final stage of the page table walk. For every PTE in the given PMD within the address range, it will free the PTE and the associated page

22 static inline void free_area_pte(pmd_t * pmd, unsigned long address,
                    unsigned long size)
 23 {
 24     pte_t * pte;
 25     unsigned long end;
 27     if (pmd_none(*pmd))
 28         return;
 29     if (pmd_bad(*pmd)) {
 30         pmd_ERROR(*pmd);
 31         pmd_clear(pmd);
 32         return;
 33     }
 34     pte = pte_offset(pmd, address);
 35     address &= ~PMD_MASK;
 36     end = address + size;
 37     if (end > PMD_SIZE)
 38         end = PMD_SIZE;
 39     do {
 40         pte_t page;
 41         page = ptep_get_and_clear(pte);
 42         address += PAGE_SIZE;
 43         pte++;
 44         if (pte_none(page))
 45             continue;
 46         if (pte_present(page)) {
 47             struct page *ptpage = pte_page(page);
 48             if (VALID_PAGE(ptpage) && 
 49                 __free_page(ptpage);
 50             continue;
 51         }
 52         printk(KERN_CRIT 
               "Whee.. Swapped out page in kernel page table\n");
 53     } while (address < end);
 54 }
22The parameters are the PMD that PTEs are been freed from, the starting address and the size of the region to free
27-28The PMD could be absent if this region is from a failed vmalloc()
29-33A PMD can be bad if it's not in main memory, it's read only or it's marked dirty or accessed
34pte is the first PTE in the address range
35Align the address to the PMD
36-38The end is either the end of the requested region or the end of the PMD, whichever occurs first
38-53Step through all PTEs, perform checks and free the PTE with its associated page
41ptep_get_and_clear() will remove a PTE from a page table and return it to the caller
42address will be the base address of the next PTE
43Move to the next PTE
44If there was no PTE, simply continue
46-51If the page is present, perform basic checks and then free it
47pte_page() uses the global mem_map to find the struct page for the PTE
48-49Make sure the page is a valid page and it is not reserved before calling __free_page() to free the physical page
50Continue to the next PTE
52If this line is reached, a PTE within the kernel address space was somehow swapped out. Kernel memory is not swappable and so is a critical error

Previous Up Next