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