arch/ppc/mm/mem_pieces.c

   1 /*
   2  *    Copyright (c) 1996 Paul Mackerras <paulus@cs.anu.edu.au>
   3  *      Changes to accommodate Power Macintoshes.
   4  *    Cort Dougan <cort@cs.nmt.edu>
   5  *      Rewrites.
   6  *    Grant Erickson <grant@lcse.umn.edu>
   7  *      General rework and split from mm/init.c.
   8  *
   9  *    Module name: mem_pieces.c
  10  *
  11  *    Description:
  12  *      Routines and data structures for manipulating and representing
  13  *      phyiscal memory extents (i.e. address/length pairs).
  14  *
  15  */
  16
  17 #include <linux/kernel.h>
  18 #include <linux/stddef.h>
  19 #include <linux/init.h>
  20 #include <asm/page.h>
  21
  22 #include "mem_pieces.h"
  23
  24 extern struct mem_pieces phys_avail;
  25
  26 static void mem_pieces_print(struct mem_pieces *);
  27
  28 /*
  29  * Scan a region for a piece of a given size with the required alignment.
  30  */
  31 void __init *
  32 mem_pieces_find(unsigned int size, unsigned int align)
  33 {
  34         int i;
  35         unsigned a, e;
  36         struct mem_pieces *mp = &phys_avail;
  37
  38         for (i = 0; i < mp->n_regions; ++i) {
  39                 a = mp->regions[i].address;
  40                 e = a + mp->regions[i].size;
  41                 a = (a + align - 1) & -align;
  42                 if (a + size <= e) {
  43                         mem_pieces_remove(mp, a, size, 1);
  44                         return (void *) __va(a);
  45                 }
  46         }
  47         panic("Couldn't find %u bytes at %u alignment\n", size, align);
  48
  49         return NULL;
  50 }
  51
  52 /*
  53  * Remove some memory from an array of pieces
  54  */
  55 void __init
  56 mem_pieces_remove(struct mem_pieces *mp, unsigned int start, unsigned int size,
  57                   int must_exist)
  58 {
  59         int i, j;
  60         unsigned int end, rs, re;
  61         struct reg_property *rp;
  62
  63         end = start + size;
  64         for (i = 0, rp = mp->regions; i < mp->n_regions; ++i, ++rp) {
  65                 if (end > rp->address && start < rp->address + rp->size)
  66                         break;
  67         }
  68         if (i >= mp->n_regions) {
  69                 if (must_exist)
  70                         printk("mem_pieces_remove: [%x,%x) not in any region\n",
  71                                start, end);
  72                 return;
  73         }
  74         for (; i < mp->n_regions && end > rp->address; ++i, ++rp) {
  75                 rs = rp->address;
  76                 re = rs + rp->size;
  77                 if (must_exist && (start < rs || end > re)) {
  78                         printk("mem_pieces_remove: bad overlap [%x,%x) with",
  79                                start, end);
  80                         mem_pieces_print(mp);
  81                         must_exist = 0;
  82                 }
  83                 if (start > rs) {
  84                         rp->size = start - rs;
  85                         if (end < re) {
  86                                 /* need to split this entry */
  87                                 if (mp->n_regions >= MEM_PIECES_MAX)
  88                                         panic("eek... mem_pieces overflow");
  89                                 for (j = mp->n_regions; j > i + 1; --j)
  90                                         mp->regions[j] = mp->regions[j-1];
  91                                 ++mp->n_regions;
  92                                 rp[1].address = end;
  93                                 rp[1].size = re - end;
  94                         }
  95                 } else {
  96                         if (end < re) {
  97                                 rp->address = end;
  98                                 rp->size = re - end;
  99                         } else {
 100                                 /* need to delete this entry */
 101                                 for (j = i; j < mp->n_regions - 1; ++j)
 102                                         mp->regions[j] = mp->regions[j+1];
 103                                 --mp->n_regions;
 104                                 --i;
 105                                 --rp;
 106                         }
 107                 }
 108         }
 109 }
 110
 111 static void __init
 112 mem_pieces_print(struct mem_pieces *mp)
 113 {
 114         int i;
 115
 116         for (i = 0; i < mp->n_regions; ++i)
 117                 printk(" [%x, %x)", mp->regions[i].address,
 118                        mp->regions[i].address + mp->regions[i].size);
 119         printk("\n");
 120 }
 121
 122 void __init
 123 mem_pieces_sort(struct mem_pieces *mp)
 124 {
 125         unsigned long a, s;
 126         int i, j;
 127
 128         for (i = 1; i < mp->n_regions; ++i) {
 129                 a = mp->regions[i].address;
 130                 s = mp->regions[i].size;
 131                 for (j = i - 1; j >= 0; --j) {
 132                         if (a >= mp->regions[j].address)
 133                                 break;
 134                         mp->regions[j+1] = mp->regions[j];
 135                 }
 136                 mp->regions[j+1].address = a;
 137                 mp->regions[j+1].size = s;
 138         }
 139 }
 140
 141 void __init
 142 mem_pieces_coalesce(struct mem_pieces *mp)
 143 {
 144         unsigned long a, s, ns;
 145         int i, j, d;
 146
 147         d = 0;
 148         for (i = 0; i < mp->n_regions; i = j) {
 149                 a = mp->regions[i].address;
 150                 s = mp->regions[i].size;
 151                 for (j = i + 1; j < mp->n_regions
 152                              && mp->regions[j].address - a <= s; ++j) {
 153                         ns = mp->regions[j].address + mp->regions[j].size - a;
 154                         if (ns > s)
 155                                 s = ns;
 156                 }
 157                 mp->regions[d].address = a;
 158                 mp->regions[d].size = s;
 159                 ++d;
 160         }
 161         mp->n_regions = d;
 162 }