home *** CD-ROM | disk | FTP | other *** search
/ Il CD di internet / CD.iso / SOURCE / KERNEL-S / V1.2 / LINUX-1.2 / LINUX-1 / linux / mm / mmap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-02  |  28.4 KB  |  976 lines
  1. /*
  2.  *    linux/mm/mmap.c
  3.  *
  4.  * Written by obz.
  5.  */
  6. #include <linux/stat.h>
  7. #include <linux/sched.h>
  8. #include <linux/kernel.h>
  9. #include <linux/mm.h>
  10. #include <linux/shm.h>
  11. #include <linux/errno.h>
  12. #include <linux/mman.h>
  13. #include <linux/string.h>
  14. #include <linux/malloc.h>
  15.  
  16. #include <asm/segment.h>
  17. #include <asm/system.h>
  18. #include <asm/pgtable.h>
  19.  
  20. static int anon_map(struct inode *, struct file *, struct vm_area_struct *);
  21.  
  22. /*
  23.  * description of effects of mapping type and prot in current implementation.
  24.  * this is due to the limited x86 page protection hardware.  The expected
  25.  * behavior is in parens:
  26.  *
  27.  * map_type    prot
  28.  *        PROT_NONE    PROT_READ    PROT_WRITE    PROT_EXEC
  29.  * MAP_SHARED    r: (no) no    r: (yes) yes    r: (no) yes    r: (no) yes
  30.  *        w: (no) no    w: (no) no    w: (yes) yes    w: (no) no
  31.  *        x: (no) no    x: (no) yes    x: (no) yes    x: (yes) yes
  32.  *        
  33.  * MAP_PRIVATE    r: (no) no    r: (yes) yes    r: (no) yes    r: (no) yes
  34.  *        w: (no) no    w: (no) no    w: (copy) copy    w: (no) no
  35.  *        x: (no) no    x: (no) yes    x: (no) yes    x: (yes) yes
  36.  *
  37.  */
  38.  
  39. pgprot_t protection_map[16] = {
  40.     __P000, __P001, __P010, __P011, __P100, __P101, __P110, __P111,
  41.     __S000, __S001, __S010, __S011, __S100, __S101, __S110, __S111
  42. };
  43.  
  44. unsigned long do_mmap(struct file * file, unsigned long addr, unsigned long len,
  45.     unsigned long prot, unsigned long flags, unsigned long off)
  46. {
  47.     int error;
  48.     struct vm_area_struct * vma;
  49.  
  50.     if ((len = PAGE_ALIGN(len)) == 0)
  51.         return addr;
  52.  
  53.     if (addr > TASK_SIZE || len > TASK_SIZE || addr > TASK_SIZE-len)
  54.         return -EINVAL;
  55.  
  56.     /* offset overflow? */
  57.     if (off + len < off)
  58.         return -EINVAL;
  59.  
  60.     /*
  61.      * do simple checking here so the lower-level routines won't have
  62.      * to. we assume access permissions have been handled by the open
  63.      * of the memory object, so we don't do any here.
  64.      */
  65.  
  66.     if (file != NULL) {
  67.         switch (flags & MAP_TYPE) {
  68.         case MAP_SHARED:
  69.             if ((prot & PROT_WRITE) && !(file->f_mode & 2))
  70.                 return -EACCES;
  71.             /* fall through */
  72.         case MAP_PRIVATE:
  73.             if (!(file->f_mode & 1))
  74.                 return -EACCES;
  75.             break;
  76.  
  77.         default:
  78.             return -EINVAL;
  79.         }
  80.         if ((flags & MAP_DENYWRITE) && (file->f_inode->i_wcount > 0))
  81.             return -ETXTBSY;
  82.     } else if ((flags & MAP_TYPE) != MAP_PRIVATE)
  83.         return -EINVAL;
  84.  
  85.     /*
  86.      * obtain the address to map to. we verify (or select) it and ensure
  87.      * that it represents a valid section of the address space.
  88.      */
  89.  
  90.     if (flags & MAP_FIXED) {
  91.         if (addr & ~PAGE_MASK)
  92.             return -EINVAL;
  93.         if (len > TASK_SIZE || addr > TASK_SIZE - len)
  94.             return -EINVAL;
  95.     } else {
  96.         addr = get_unmapped_area(len);
  97.         if (!addr)
  98.             return -ENOMEM;
  99.     }
  100.  
  101.     /*
  102.      * determine the object being mapped and call the appropriate
  103.      * specific mapper. the address has already been validated, but
  104.      * not unmapped, but the maps are removed from the list.
  105.      */
  106.     if (file && (!file->f_op || !file->f_op->mmap))
  107.         return -ENODEV;
  108.  
  109.     vma = (struct vm_area_struct *)kmalloc(sizeof(struct vm_area_struct),
  110.         GFP_KERNEL);
  111.     if (!vma)
  112.         return -ENOMEM;
  113.  
  114.     vma->vm_task = current;
  115.     vma->vm_start = addr;
  116.     vma->vm_end = addr + len;
  117.     vma->vm_flags = prot & (VM_READ | VM_WRITE | VM_EXEC);
  118.     vma->vm_flags |= flags & (VM_GROWSDOWN | VM_DENYWRITE | VM_EXECUTABLE);
  119.  
  120.     if (file) {
  121.         if (file->f_mode & 1)
  122.             vma->vm_flags |= VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
  123.         if (flags & MAP_SHARED) {
  124.             vma->vm_flags |= VM_SHARED | VM_MAYSHARE;
  125.             /*
  126.              * This looks strange, but when we don't have the file open
  127.              * for writing, we can demote the shared mapping to a simpler
  128.              * private mapping. That also takes care of a security hole
  129.              * with ptrace() writing to a shared mapping without write
  130.              * permissions.
  131.              *
  132.              * We leave the VM_MAYSHARE bit on, just to get correct output
  133.              * from /proc/xxx/maps..
  134.              */
  135.             if (!(file->f_mode & 2))
  136.                 vma->vm_flags &= ~(VM_MAYWRITE | VM_SHARED);
  137.         }
  138.     } else
  139.         vma->vm_flags |= VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
  140.     vma->vm_page_prot = protection_map[vma->vm_flags & 0x0f];
  141.     vma->vm_ops = NULL;
  142.     vma->vm_offset = off;
  143.     vma->vm_inode = NULL;
  144.     vma->vm_pte = 0;
  145.  
  146.     do_munmap(addr, len);    /* Clear old maps */
  147.  
  148.     if (file)
  149.         error = file->f_op->mmap(file->f_inode, file, vma);
  150.     else
  151.         error = anon_map(NULL, NULL, vma);
  152.     
  153.     if (error) {
  154.         kfree(vma);
  155.         return error;
  156.     }
  157.     insert_vm_struct(current, vma);
  158.     merge_segments(current, vma->vm_start, vma->vm_end);
  159.     return addr;
  160. }
  161.  
  162. /*
  163.  * Get an address range which is currently unmapped.
  164.  * For mmap() without MAP_FIXED and shmat() with addr=0.
  165.  * Return value 0 means ENOMEM.
  166.  */
  167. unsigned long get_unmapped_area(unsigned long len)
  168. {
  169.     struct vm_area_struct * vmm;
  170.     unsigned long gap_start = 0, gap_end;
  171.  
  172.     for (vmm = current->mm->mmap; ; vmm = vmm->vm_next) {
  173.         if (gap_start < SHM_RANGE_START)
  174.             gap_start = SHM_RANGE_START;
  175.         if (!vmm || ((gap_end = vmm->vm_start) > SHM_RANGE_END))
  176.             gap_end = SHM_RANGE_END;
  177.         gap_start = PAGE_ALIGN(gap_start);
  178.         gap_end &= PAGE_MASK;
  179.         if ((gap_start <= gap_end) && (gap_end - gap_start >= len))
  180.             return gap_start;
  181.         if (!vmm)
  182.             return 0;
  183.         gap_start = vmm->vm_end;
  184.     }
  185. }
  186.  
  187. asmlinkage int sys_mmap(unsigned long *buffer)
  188. {
  189.     int error;
  190.     unsigned long flags;
  191.     struct file * file = NULL;
  192.  
  193.     error = verify_area(VERIFY_READ, buffer, 6*sizeof(long));
  194.     if (error)
  195.         return error;
  196.     flags = get_fs_long(buffer+3);
  197.     if (!(flags & MAP_ANONYMOUS)) {
  198.         unsigned long fd = get_fs_long(buffer+4);
  199.         if (fd >= NR_OPEN || !(file = current->files->fd[fd]))
  200.             return -EBADF;
  201.     }
  202.     return do_mmap(file, get_fs_long(buffer), get_fs_long(buffer+1),
  203.         get_fs_long(buffer+2), flags, get_fs_long(buffer+5));
  204. }
  205.  
  206.  
  207. /*
  208.  * Searching a VMA in the linear list task->mm->mmap is horribly slow.
  209.  * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search
  210.  * from O(n) to O(log n), where n is the number of VMAs of the task
  211.  * (typically around 6, but may reach 3000 in some cases).
  212.  * Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>.
  213.  */
  214.  
  215. /* We keep the list and tree sorted by address. */
  216. #define vm_avl_key    vm_end
  217. #define vm_avl_key_t    unsigned long    /* typeof(vma->avl_key) */
  218.  
  219. /*
  220.  * task->mm->mmap_avl is the AVL tree corresponding to task->mm->mmap
  221.  * or, more exactly, its root.
  222.  * A vm_area_struct has the following fields:
  223.  *   vm_avl_left     left son of a tree node
  224.  *   vm_avl_right    right son of a tree node
  225.  *   vm_avl_height   1+max(heightof(left),heightof(right))
  226.  * The empty tree is represented as NULL.
  227.  */
  228. #define avl_empty    (struct vm_area_struct *) NULL
  229.  
  230. /* Since the trees are balanced, their height will never be large. */
  231. #define avl_maxheight    41    /* why this? a small exercise */
  232. #define heightof(tree)    ((tree) == avl_empty ? 0 : (tree)->vm_avl_height)
  233. /*
  234.  * Consistency and balancing rules:
  235.  * 1. tree->vm_avl_height == 1+max(heightof(tree->vm_avl_left),heightof(tree->vm_avl_right))
  236.  * 2. abs( heightof(tree->vm_avl_left) - heightof(tree->vm_avl_right) ) <= 1
  237.  * 3. foreach node in tree->vm_avl_left: node->vm_avl_key <= tree->vm_avl_key,
  238.  *    foreach node in tree->vm_avl_right: node->vm_avl_key >= tree->vm_avl_key.
  239.  */
  240.  
  241. /* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
  242. struct vm_area_struct * find_vma (struct task_struct * task, unsigned long addr)
  243. {
  244. #if 0 /* equivalent, but slow */
  245.     struct vm_area_struct * vma;
  246.  
  247.     for (vma = task->mm->mmap ; ; vma = vma->vm_next) {
  248.         if (!vma)
  249.             return NULL;
  250.         if (vma->vm_end > addr)
  251.             return vma;
  252.     }
  253. #else
  254.     struct vm_area_struct * result = NULL;
  255.     struct vm_area_struct * tree;
  256.  
  257.     for (tree = task->mm->mmap_avl ; ; ) {
  258.         if (tree == avl_empty)
  259.             return result;
  260.         if (tree->vm_end > addr) {
  261.             if (tree->vm_start <= addr)
  262.                 return tree;
  263.             result = tree;
  264.             tree = tree->vm_avl_left;
  265.         } else
  266.             tree = tree->vm_avl_right;
  267.     }
  268. #endif
  269. }
  270.  
  271. /* Look up the first VMA which intersects the interval start_addr..end_addr-1,
  272.    NULL if none.  Assume start_addr < end_addr. */
  273. struct vm_area_struct * find_vma_intersection (struct task_struct * task, unsigned long start_addr, unsigned long end_addr)
  274. {
  275.     struct vm_area_struct * vma;
  276.  
  277. #if 0 /* equivalent, but slow */
  278.     for (vma = task->mm->mmap; vma; vma = vma->vm_next) {
  279.         if (end_addr <= vma->vm_start)
  280.             break;
  281.         if (start_addr < vma->vm_end)
  282.             return vma;
  283.     }
  284.     return NULL;
  285. #else
  286.     vma = find_vma(task,start_addr);
  287.     if (!vma || end_addr <= vma->vm_start)
  288.         return NULL;
  289.     return vma;
  290. #endif
  291. }
  292.  
  293. /* Look up the nodes at the left and at the right of a given node. */
  294. static void avl_neighbours (struct vm_area_struct * node, struct vm_area_struct * tree, struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
  295. {
  296.     vm_avl_key_t key = node->vm_avl_key;
  297.  
  298.     *to_the_left = *to_the_right = NULL;
  299.     for (;;) {
  300.         if (tree == avl_empty) {
  301.             printk("avl_neighbours: node not found in the tree\n");
  302.             return;
  303.         }
  304.         if (key == tree->vm_avl_key)
  305.             break;
  306.         if (key < tree->vm_avl_key) {
  307.             *to_the_right = tree;
  308.             tree = tree->vm_avl_left;
  309.         } else {
  310.             *to_the_left = tree;
  311.             tree = tree->vm_avl_right;
  312.         }
  313.     }
  314.     if (tree != node) {
  315.         printk("avl_neighbours: node not exactly found in the tree\n");
  316.         return;
  317.     }
  318.     if (tree->vm_avl_left != avl_empty) {
  319.         struct vm_area_struct * node;
  320.         for (node = tree->vm_avl_left; node->vm_avl_right != avl_empty; node = node->vm_avl_right)
  321.             continue;
  322.         *to_the_left = node;
  323.     }
  324.     if (tree->vm_avl_right != avl_empty) {
  325.         struct vm_area_struct * node;
  326.         for (node = tree->vm_avl_right; node->vm_avl_left != avl_empty; node = node->vm_avl_left)
  327.             continue;
  328.         *to_the_right = node;
  329.     }
  330.     if ((*to_the_left && ((*to_the_left)->vm_next != node)) || (node->vm_next != *to_the_right))
  331.         printk("avl_neighbours: tree inconsistent with list\n");
  332. }
  333.  
  334. /*
  335.  * Rebalance a tree.
  336.  * After inserting or deleting a node of a tree we have a sequence of subtrees
  337.  * nodes[0]..nodes[k-1] such that
  338.  * nodes[0] is the root and nodes[i+1] = nodes[i]->{vm_avl_left|vm_avl_right}.
  339.  */
  340. static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count)
  341. {
  342.     for ( ; count > 0 ; count--) {
  343.         struct vm_area_struct ** nodeplace = *--nodeplaces_ptr;
  344.         struct vm_area_struct * node = *nodeplace;
  345.         struct vm_area_struct * nodeleft = node->vm_avl_left;
  346.         struct vm_area_struct * noderight = node->vm_avl_right;
  347.         int heightleft = heightof(nodeleft);
  348.         int heightright = heightof(noderight);
  349.         if (heightright + 1 < heightleft) {
  350.             /*                                                      */
  351.             /*                            *                         */
  352.             /*                          /   \                       */
  353.             /*                       n+2      n                     */
  354.             /*                                                      */
  355.             struct vm_area_struct * nodeleftleft = nodeleft->vm_avl_left;
  356.             struct vm_area_struct * nodeleftright = nodeleft->vm_avl_right;
  357.             int heightleftright = heightof(nodeleftright);
  358.             if (heightof(nodeleftleft) >= heightleftright) {
  359.                 /*                                                        */
  360.                 /*                *                    n+2|n+3            */
  361.                 /*              /   \                  /    \             */
  362.                 /*           n+2      n      -->      /   n+1|n+2         */
  363.                 /*           / \                      |    /    \         */
  364.                 /*         n+1 n|n+1                 n+1  n|n+1  n        */
  365.                 /*                                                        */
  366.                 node->vm_avl_left = nodeleftright; nodeleft->vm_avl_right = node;
  367.                 nodeleft->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightleftright);
  368.                 *nodeplace = nodeleft;
  369.             } else {
  370.                 /*                                                        */
  371.                 /*                *                     n+2               */
  372.                 /*              /   \                 /     \             */
  373.                 /*           n+2      n      -->    n+1     n+1           */
  374.                 /*           / \                    / \     / \           */
  375.                 /*          n  n+1                 n   L   R   n          */
  376.                 /*             / \                                        */
  377.                 /*            L   R                                       */
  378.                 /*                                                        */
  379.                 nodeleft->vm_avl_right = nodeleftright->vm_avl_left;
  380.                 node->vm_avl_left = nodeleftright->vm_avl_right;
  381.                 nodeleftright->vm_avl_left = nodeleft;
  382.                 nodeleftright->vm_avl_right = node;
  383.                 nodeleft->vm_avl_height = node->vm_avl_height = heightleftright;
  384.                 nodeleftright->vm_avl_height = heightleft;
  385.                 *nodeplace = nodeleftright;
  386.             }
  387.         }
  388.         else if (heightleft + 1 < heightright) {
  389.             /* similar to the above, just interchange 'left' <--> 'right' */
  390.             struct vm_area_struct * noderightright = noderight->vm_avl_right;
  391.             struct vm_area_struct * noderightleft = noderight->vm_avl_left;
  392.             int heightrightleft = heightof(noderightleft);
  393.             if (heightof(noderightright) >= heightrightleft) {
  394.                 node->vm_avl_right = noderightleft; noderight->vm_avl_left = node;
  395.                 noderight->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightrightleft);
  396.                 *nodeplace = noderight;
  397.             } else {
  398.                 noderight->vm_avl_left = noderightleft->vm_avl_right;
  399.                 node->vm_avl_right = noderightleft->vm_avl_left;
  400.                 noderightleft->vm_avl_right = noderight;
  401.                 noderightleft->vm_avl_left = node;
  402.                 noderight->vm_avl_height = node->vm_avl_height = heightrightleft;
  403.                 noderightleft->vm_avl_height = heightright;
  404.                 *nodeplace = noderightleft;
  405.             }
  406.         }
  407.         else {
  408.             int height = (heightleft<heightright ? heightright : heightleft) + 1;
  409.             if (height == node->vm_avl_height)
  410.                 break;
  411.             node->vm_avl_height = height;
  412.         }
  413.     }
  414. }
  415.  
  416. /* Insert a node into a tree. */
  417. static void avl_insert (struct vm_area_struct * new_node, struct vm_area_struct ** ptree)
  418. {
  419.     vm_avl_key_t key = new_node->vm_avl_key;
  420.     struct vm_area_struct ** nodeplace = ptree;
  421.     struct vm_area_struct ** stack[avl_maxheight];
  422.     int stack_count = 0;
  423.     struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
  424.     for (;;) {
  425.         struct vm_area_struct * node = *nodeplace;
  426.         if (node == avl_empty)
  427.             break;
  428.         *stack_ptr++ = nodeplace; stack_count++;
  429.         if (key < node->vm_avl_key)
  430.             nodeplace = &node->vm_avl_left;
  431.         else
  432.             nodeplace = &node->vm_avl_right;
  433.     }
  434.     new_node->vm_avl_left = avl_empty;
  435.     new_node->vm_avl_right = avl_empty;
  436.     new_node->vm_avl_height = 1;
  437.     *nodeplace = new_node;
  438.     avl_rebalance(stack_ptr,stack_count);
  439. }
  440.  
  441. /* Insert a node into a tree, and
  442.  * return the node to the left of it and the node to the right of it.
  443.  */
  444. static void avl_insert_neighbours (struct vm_area_struct * new_node, struct vm_area_struct ** ptree,
  445.     struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
  446. {
  447.     vm_avl_key_t key = new_node->vm_avl_key;
  448.     struct vm_area_struct ** nodeplace = ptree;
  449.     struct vm_area_struct ** stack[avl_maxheight];
  450.     int stack_count = 0;
  451.     struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
  452.     *to_the_left = *to_the_right = NULL;
  453.     for (;;) {
  454.         struct vm_area_struct * node = *nodeplace;
  455.         if (node == avl_empty)
  456.             break;
  457.         *stack_ptr++ = nodeplace; stack_count++;
  458.         if (key < node->vm_avl_key) {
  459.             *to_the_right = node;
  460.             nodeplace = &node->vm_avl_left;
  461.         } else {
  462.             *to_the_left = node;
  463.             nodeplace = &node->vm_avl_right;
  464.         }
  465.     }
  466.     new_node->vm_avl_left = avl_empty;
  467.     new_node->vm_avl_right = avl_empty;
  468.     new_node->vm_avl_height = 1;
  469.     *nodeplace = new_node;
  470.     avl_rebalance(stack_ptr,stack_count);
  471. }
  472.  
  473. /* Removes a node out of a tree. */
  474. static void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree)
  475. {
  476.     vm_avl_key_t key = node_to_delete->vm_avl_key;
  477.     struct vm_area_struct ** nodeplace = ptree;
  478.     struct vm_area_struct ** stack[avl_maxheight];
  479.     int stack_count = 0;
  480.     struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
  481.     struct vm_area_struct ** nodeplace_to_delete;
  482.     for (;;) {
  483.         struct vm_area_struct * node = *nodeplace;
  484.         if (node == avl_empty) {
  485.             /* what? node_to_delete not found in tree? */
  486.             printk("avl_remove: node to delete not found in tree\n");
  487.             return;
  488.         }
  489.         *stack_ptr++ = nodeplace; stack_count++;
  490.         if (key == node->vm_avl_key)
  491.             break;
  492.         if (key < node->vm_avl_key)
  493.             nodeplace = &node->vm_avl_left;
  494.         else
  495.             nodeplace = &node->vm_avl_right;
  496.     }
  497.     nodeplace_to_delete = nodeplace;
  498.     /* Have to remove node_to_delete = *nodeplace_to_delete. */
  499.     if (node_to_delete->vm_avl_left == avl_empty) {
  500.         *nodeplace_to_delete = node_to_delete->vm_avl_right;
  501.         stack_ptr--; stack_count--;
  502.     } else {
  503.         struct vm_area_struct *** stack_ptr_to_delete = stack_ptr;
  504.         struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left;
  505.         struct vm_area_struct * node;
  506.         for (;;) {
  507.             node = *nodeplace;
  508.             if (node->vm_avl_right == avl_empty)
  509.                 break;
  510.             *stack_ptr++ = nodeplace; stack_count++;
  511.             nodeplace = &node->vm_avl_right;
  512.         }
  513.         *nodeplace = node->vm_avl_left;
  514.         /* node replaces node_to_delete */
  515.         node->vm_avl_left = node_to_delete->vm_avl_left;
  516.         node->vm_avl_right = node_to_delete->vm_avl_right;
  517.         node->vm_avl_height = node_to_delete->vm_avl_height;
  518.         *nodeplace_to_delete = node; /* replace node_to_delete */
  519.         *stack_ptr_to_delete = &node->vm_avl_left; /* replace &node_to_delete->vm_avl_left */
  520.     }
  521.     avl_rebalance(stack_ptr,stack_count);
  522. }
  523.  
  524. #ifdef DEBUG_AVL
  525.  
  526. /* print a list */
  527. static void printk_list (struct vm_area_struct * vma)
  528. {
  529.     printk("[");
  530.     while (vma) {
  531.         printk("%08lX-%08lX", vma->vm_start, vma->vm_end);
  532.         vma = vma->vm_next;
  533.         if (!vma)
  534.             break;
  535.         printk(" ");
  536.     }
  537.     printk("]");
  538. }
  539.  
  540. /* print a tree */
  541. static void printk_avl (struct vm_area_struct * tree)
  542. {
  543.     if (tree != avl_empty) {
  544.         printk("(");
  545.         if (tree->vm_avl_left != avl_empty) {
  546.             printk_avl(tree->vm_avl_left);
  547.             printk("<");
  548.         }
  549.         printk("%08lX-%08lX", tree->vm_start, tree->vm_end);
  550.         if (tree->vm_avl_right != avl_empty) {
  551.             printk(">");
  552.             printk_avl(tree->vm_avl_right);
  553.         }
  554.         printk(")");
  555.     }
  556. }
  557.  
  558. static char *avl_check_point = "somewhere";
  559.  
  560. /* check a tree's consistency and balancing */
  561. static void avl_checkheights (struct vm_area_struct * tree)
  562. {
  563.     int h, hl, hr;
  564.  
  565.     if (tree == avl_empty)
  566.         return;
  567.     avl_checkheights(tree->vm_avl_left);
  568.     avl_checkheights(tree->vm_avl_right);
  569.     h = tree->vm_avl_height;
  570.     hl = heightof(tree->vm_avl_left);
  571.     hr = heightof(tree->vm_avl_right);
  572.     if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
  573.         return;
  574.     if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
  575.         return;
  576.     printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);
  577. }
  578.  
  579. /* check that all values stored in a tree are < key */
  580. static void avl_checkleft (struct vm_area_struct * tree, vm_avl_key_t key)
  581. {
  582.     if (tree == avl_empty)
  583.         return;
  584.     avl_checkleft(tree->vm_avl_left,key);
  585.     avl_checkleft(tree->vm_avl_right,key);
  586.     if (tree->vm_avl_key < key)
  587.         return;
  588.     printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
  589. }
  590.  
  591. /* check that all values stored in a tree are > key */
  592. static void avl_checkright (struct vm_area_struct * tree, vm_avl_key_t key)
  593. {
  594.     if (tree == avl_empty)
  595.         return;
  596.     avl_checkright(tree->vm_avl_left,key);
  597.     avl_checkright(tree->vm_avl_right,key);
  598.     if (tree->vm_avl_key > key)
  599.         return;
  600.     printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
  601. }
  602.  
  603. /* check that all values are properly increasing */
  604. static void avl_checkorder (struct vm_area_struct * tree)
  605. {
  606.     if (tree == avl_empty)
  607.         return;
  608.     avl_checkorder(tree->vm_avl_left);
  609.     avl_checkorder(tree->vm_avl_right);
  610.     avl_checkleft(tree->vm_avl_left,tree->vm_avl_key);
  611.     avl_checkright(tree->vm_avl_right,tree->vm_avl_key);
  612. }
  613.  
  614. /* all checks */
  615. static void avl_check (struct task_struct * task, char *caller)
  616. {
  617.     avl_check_point = caller;
  618. /*    printk("task \"%s\", %s\n",task->comm,caller); */
  619. /*    printk("task \"%s\" list: ",task->comm); printk_list(task->mm->mmap); printk("\n"); */
  620. /*    printk("task \"%s\" tree: ",task->comm); printk_avl(task->mm->mmap_avl); printk("\n"); */
  621.     avl_checkheights(task->mm->mmap_avl);
  622.     avl_checkorder(task->mm->mmap_avl);
  623. }
  624.  
  625. #endif
  626.  
  627.  
  628. /*
  629.  * Normal function to fix up a mapping
  630.  * This function is the default for when an area has no specific
  631.  * function.  This may be used as part of a more specific routine.
  632.  * This function works out what part of an area is affected and
  633.  * adjusts the mapping information.  Since the actual page
  634.  * manipulation is done in do_mmap(), none need be done here,
  635.  * though it would probably be more appropriate.
  636.  *
  637.  * By the time this function is called, the area struct has been
  638.  * removed from the process mapping list, so it needs to be
  639.  * reinserted if necessary.
  640.  *
  641.  * The 4 main cases are:
  642.  *    Unmapping the whole area
  643.  *    Unmapping from the start of the segment to a point in it
  644.  *    Unmapping from an intermediate point to the end
  645.  *    Unmapping between to intermediate points, making a hole.
  646.  *
  647.  * Case 4 involves the creation of 2 new areas, for each side of
  648.  * the hole.
  649.  */
  650. void unmap_fixup(struct vm_area_struct *area,
  651.          unsigned long addr, size_t len)
  652. {
  653.     struct vm_area_struct *mpnt;
  654.     unsigned long end = addr + len;
  655.  
  656.     if (addr < area->vm_start || addr >= area->vm_end ||
  657.         end <= area->vm_start || end > area->vm_end ||
  658.         end < addr)
  659.     {
  660.         printk("unmap_fixup: area=%lx-%lx, unmap %lx-%lx!!\n",
  661.                area->vm_start, area->vm_end, addr, end);
  662.         return;
  663.     }
  664.  
  665.     /* Unmapping the whole area */
  666.     if (addr == area->vm_start && end == area->vm_end) {
  667.         if (area->vm_ops && area->vm_ops->close)
  668.             area->vm_ops->close(area);
  669.         if (area->vm_inode)
  670.             iput(area->vm_inode);
  671.         return;
  672.     }
  673.  
  674.     /* Work out to one of the ends */
  675.     if (end == area->vm_end)
  676.         area->vm_end = addr;
  677.     else
  678.     if (addr == area->vm_start) {
  679.         area->vm_offset += (end - area->vm_start);
  680.         area->vm_start = end;
  681.     }
  682.     else {
  683.     /* Unmapping a hole: area->vm_start < addr <= end < area->vm_end */
  684.         /* Add end mapping -- leave beginning for below */
  685.         mpnt = (struct vm_area_struct *)kmalloc(sizeof(*mpnt), GFP_KERNEL);
  686.  
  687.         if (!mpnt)
  688.             return;
  689.         *mpnt = *area;
  690.         mpnt->vm_offset += (end - area->vm_start);
  691.         mpnt->vm_start = end;
  692.         if (mpnt->vm_inode)
  693.             mpnt->vm_inode->i_count++;
  694.         if (mpnt->vm_ops && mpnt->vm_ops->open)
  695.             mpnt->vm_ops->open(mpnt);
  696.         area->vm_end = addr;    /* Truncate area */
  697.         insert_vm_struct(current, mpnt);
  698.     }
  699.  
  700.     /* construct whatever mapping is needed */
  701.     mpnt = (struct vm_area_struct *)kmalloc(sizeof(*mpnt), GFP_KERNEL);
  702.     if (!mpnt)
  703.         return;
  704.     *mpnt = *area;
  705.     if (mpnt->vm_ops && mpnt->vm_ops->open)
  706.         mpnt->vm_ops->open(mpnt);
  707.     if (area->vm_ops && area->vm_ops->close) {
  708.         area->vm_end = area->vm_start;
  709.         area->vm_ops->close(area);
  710.     }
  711.     insert_vm_struct(current, mpnt);
  712. }
  713.  
  714. asmlinkage int sys_munmap(unsigned long addr, size_t len)
  715. {
  716.     return do_munmap(addr, len);
  717. }
  718.  
  719. /*
  720.  * Munmap is split into 2 main parts -- this part which finds
  721.  * what needs doing, and the areas themselves, which do the
  722.  * work.  This now handles partial unmappings.
  723.  * Jeremy Fitzhardine <jeremy@sw.oz.au>
  724.  */
  725. int do_munmap(unsigned long addr, size_t len)
  726. {
  727.     struct vm_area_struct *mpnt, *prev, *next, **npp, *free;
  728.  
  729.     if ((addr & ~PAGE_MASK) || addr > TASK_SIZE || len > TASK_SIZE-addr)
  730.         return -EINVAL;
  731.  
  732.     if ((len = PAGE_ALIGN(len)) == 0)
  733.         return 0;
  734.  
  735.     /*
  736.      * Check if this memory area is ok - put it on the temporary
  737.      * list if so..  The checks here are pretty simple --
  738.      * every area affected in some way (by any overlap) is put
  739.      * on the list.  If nothing is put on, nothing is affected.
  740.      */
  741.     mpnt = find_vma(current, addr);
  742.     if (!mpnt)
  743.         return 0;
  744.     avl_neighbours(mpnt, current->mm->mmap_avl, &prev, &next);
  745.     /* we have  prev->vm_next == mpnt && mpnt->vm_next = next */
  746.     /* and  addr < mpnt->vm_end  */
  747.  
  748.     npp = (prev ? &prev->vm_next : ¤t->mm->mmap);
  749.     free = NULL;
  750.     for ( ; mpnt && mpnt->vm_start < addr+len; mpnt = *npp) {
  751.         *npp = mpnt->vm_next;
  752.         mpnt->vm_next = free;
  753.         free = mpnt;
  754.         avl_remove(mpnt, ¤t->mm->mmap_avl);
  755.     }
  756.  
  757.     if (free == NULL)
  758.         return 0;
  759.  
  760.     /*
  761.      * Ok - we have the memory areas we should free on the 'free' list,
  762.      * so release them, and unmap the page range..
  763.      * If the one of the segments is only being partially unmapped,
  764.      * it will put new vm_area_struct(s) into the address space.
  765.      */
  766.     while (free) {
  767.         unsigned long st, end;
  768.  
  769.         mpnt = free;
  770.         free = free->vm_next;
  771.  
  772.         remove_shared_vm_struct(mpnt);
  773.  
  774.         st = addr < mpnt->vm_start ? mpnt->vm_start : addr;
  775.         end = addr+len;
  776.         end = end > mpnt->vm_end ? mpnt->vm_end : end;
  777.  
  778.         if (mpnt->vm_ops && mpnt->vm_ops->unmap)
  779.             mpnt->vm_ops->unmap(mpnt, st, end-st);
  780.  
  781.         unmap_fixup(mpnt, st, end-st);
  782.         kfree(mpnt);
  783.     }
  784.  
  785.     unmap_page_range(addr, len);
  786.     return 0;
  787. }
  788.  
  789. /* Build the AVL tree corresponding to the VMA list. */
  790. void build_mmap_avl(struct task_struct * task)
  791. {
  792.     struct vm_area_struct * vma;
  793.  
  794.     task->mm->mmap_avl = NULL;
  795.     for (vma = task->mm->mmap; vma; vma = vma->vm_next)
  796.         avl_insert(vma, &task->mm->mmap_avl);
  797. }
  798.  
  799. /* Release all mmaps. */
  800. void exit_mmap(struct task_struct * task)
  801. {
  802.     struct vm_area_struct * mpnt;
  803.  
  804.     mpnt = task->mm->mmap;
  805.     task->mm->mmap = NULL;
  806.     task->mm->mmap_avl = NULL;
  807.     while (mpnt) {
  808.         struct vm_area_struct * next = mpnt->vm_next;
  809.         if (mpnt->vm_ops && mpnt->vm_ops->close)
  810.             mpnt->vm_ops->close(mpnt);
  811.         remove_shared_vm_struct(mpnt);
  812.         if (mpnt->vm_inode)
  813.             iput(mpnt->vm_inode);
  814.         kfree(mpnt);
  815.         mpnt = next;
  816.     }
  817. }
  818.  
  819. /*
  820.  * Insert vm structure into process list sorted by address
  821.  * and into the inode's i_mmap ring.
  822.  */
  823. void insert_vm_struct(struct task_struct *t, struct vm_area_struct *vmp)
  824. {
  825.     struct vm_area_struct *share;
  826.     struct inode * inode;
  827.  
  828. #if 0 /* equivalent, but slow */
  829.     struct vm_area_struct **p, *mpnt;
  830.  
  831.     p = &t->mm->mmap;
  832.     while ((mpnt = *p) != NULL) {
  833.         if (mpnt->vm_start > vmp->vm_start)
  834.             break;
  835.         if (mpnt->vm_end > vmp->vm_start)
  836.             printk("insert_vm_struct: overlapping memory areas\n");
  837.         p = &mpnt->vm_next;
  838.     }
  839.     vmp->vm_next = mpnt;
  840.     *p = vmp;
  841. #else
  842.     struct vm_area_struct * prev, * next;
  843.  
  844.     avl_insert_neighbours(vmp, &t->mm->mmap_avl, &prev, &next);
  845.     if ((prev ? prev->vm_next : t->mm->mmap) != next)
  846.         printk("insert_vm_struct: tree inconsistent with list\n");
  847.     if (prev)
  848.         prev->vm_next = vmp;
  849.     else
  850.         t->mm->mmap = vmp;
  851.     vmp->vm_next = next;
  852. #endif
  853.  
  854.     inode = vmp->vm_inode;
  855.     if (!inode)
  856.         return;
  857.  
  858.     /* insert vmp into inode's circular share list */
  859.     if ((share = inode->i_mmap)) {
  860.         vmp->vm_next_share = share->vm_next_share;
  861.         vmp->vm_next_share->vm_prev_share = vmp;
  862.         share->vm_next_share = vmp;
  863.         vmp->vm_prev_share = share;
  864.     } else
  865.         inode->i_mmap = vmp->vm_next_share = vmp->vm_prev_share = vmp;
  866. }
  867.  
  868. /*
  869.  * Remove one vm structure from the inode's i_mmap ring.
  870.  */
  871. void remove_shared_vm_struct(struct vm_area_struct *mpnt)
  872. {
  873.     struct inode * inode = mpnt->vm_inode;
  874.  
  875.     if (!inode)
  876.         return;
  877.  
  878.     if (mpnt->vm_next_share == mpnt) {
  879.         if (inode->i_mmap != mpnt)
  880.             printk("Inode i_mmap ring corrupted\n");
  881.         inode->i_mmap = NULL;
  882.         return;
  883.     }
  884.  
  885.     if (inode->i_mmap == mpnt)
  886.         inode->i_mmap = mpnt->vm_next_share;
  887.  
  888.     mpnt->vm_prev_share->vm_next_share = mpnt->vm_next_share;
  889.     mpnt->vm_next_share->vm_prev_share = mpnt->vm_prev_share;
  890. }
  891.  
  892. /*
  893.  * Merge the list of memory segments if possible.
  894.  * Redundant vm_area_structs are freed.
  895.  * This assumes that the list is ordered by address.
  896.  * We don't need to traverse the entire list, only those segments
  897.  * which intersect or are adjacent to a given interval.
  898.  */
  899. void merge_segments (struct task_struct * task, unsigned long start_addr, unsigned long end_addr)
  900. {
  901.     struct vm_area_struct *prev, *mpnt, *next;
  902.  
  903.     mpnt = find_vma(task, start_addr);
  904.     if (!mpnt)
  905.         return;
  906.     avl_neighbours(mpnt, task->mm->mmap_avl, &prev, &next);
  907.     /* we have  prev->vm_next == mpnt && mpnt->vm_next = next */
  908.  
  909.     if (!prev) {
  910.         prev = mpnt;
  911.         mpnt = next;
  912.     }
  913.  
  914.     /* prev and mpnt cycle through the list, as long as
  915.      * start_addr < mpnt->vm_end && prev->vm_start < end_addr
  916.      */
  917.     for ( ; mpnt && prev->vm_start < end_addr ; prev = mpnt, mpnt = next) {
  918. #if 0
  919.         printk("looping in merge_segments, mpnt=0x%lX\n", (unsigned long) mpnt);
  920. #endif
  921.  
  922.         next = mpnt->vm_next;
  923.  
  924.         /*
  925.          * To share, we must have the same inode, operations.. 
  926.          */
  927.         if (mpnt->vm_inode != prev->vm_inode)
  928.             continue;
  929.         if (mpnt->vm_pte != prev->vm_pte)
  930.             continue;
  931.         if (mpnt->vm_ops != prev->vm_ops)
  932.             continue;
  933.         if (mpnt->vm_flags != prev->vm_flags)
  934.             continue;
  935.         if (prev->vm_end != mpnt->vm_start)
  936.             continue;
  937.         /*
  938.          * and if we have an inode, the offsets must be contiguous..
  939.          */
  940.         if ((mpnt->vm_inode != NULL) || (mpnt->vm_flags & VM_SHM)) {
  941.             if (prev->vm_offset + prev->vm_end - prev->vm_start != mpnt->vm_offset)
  942.                 continue;
  943.         }
  944.  
  945.         /*
  946.          * merge prev with mpnt and set up pointers so the new
  947.          * big segment can possibly merge with the next one.
  948.          * The old unused mpnt is freed.
  949.          */
  950.         avl_remove(mpnt, &task->mm->mmap_avl);
  951.         prev->vm_end = mpnt->vm_end;
  952.         prev->vm_next = mpnt->vm_next;
  953.         if (mpnt->vm_ops && mpnt->vm_ops->close) {
  954.             mpnt->vm_offset += mpnt->vm_end - mpnt->vm_start;
  955.             mpnt->vm_start = mpnt->vm_end;
  956.             mpnt->vm_ops->close(mpnt);
  957.         }
  958.         remove_shared_vm_struct(mpnt);
  959.         if (mpnt->vm_inode)
  960.             mpnt->vm_inode->i_count--;
  961.         kfree_s(mpnt, sizeof(*mpnt));
  962.         mpnt = prev;
  963.     }
  964. }
  965.  
  966. /*
  967.  * Map memory not associated with any file into a process
  968.  * address space.  Adjacent memory is merged.
  969.  */
  970. static int anon_map(struct inode *ino, struct file * file, struct vm_area_struct * vma)
  971. {
  972.     if (zeromap_page_range(vma->vm_start, vma->vm_end - vma->vm_start, vma->vm_page_prot))
  973.         return -ENOMEM;
  974.     return 0;
  975. }
  976.