2 * Copyright (c) 1996 Paul Mackerras <paulus@cs.anu.edu.au>
3 * Changes to accommodate Power Macintoshes.
4 * Cort Dougan <cort@cs.nmt.edu>
6 * Grant Erickson <grant@lcse.umn.edu>
7 * General rework and split from mm/init.c.
9 * Module name: mem_pieces.c
12 * Routines and data structures for manipulating and representing
13 * phyiscal memory extents (i.e. address/length pairs).
17 #include <linux/config.h>
18 #include <linux/kernel.h>
19 #include <linux/stddef.h>
20 #include <linux/init.h>
23 #include "mem_pieces.h"
25 extern struct mem_pieces phys_avail
;
27 static void mem_pieces_print(struct mem_pieces
*);
30 * Scan a region for a piece of a given size with the required alignment.
33 mem_pieces_find(unsigned int size
, unsigned int align
)
37 struct mem_pieces
*mp
= &phys_avail
;
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
;
44 mem_pieces_remove(mp
, a
, size
, 1);
45 return (void *) __va(a
);
48 panic("Couldn't find %u bytes at %u alignment\n", size
, align
);
54 * Remove some memory from an array of pieces
57 mem_pieces_remove(struct mem_pieces
*mp
, unsigned int start
, unsigned int size
,
61 unsigned int end
, rs
, re
;
62 struct reg_property
*rp
;
65 for (i
= 0, rp
= mp
->regions
; i
< mp
->n_regions
; ++i
, ++rp
) {
66 if (end
> rp
->address
&& start
< rp
->address
+ rp
->size
)
69 if (i
>= mp
->n_regions
) {
71 printk("mem_pieces_remove: [%x,%x) not in any region\n",
75 for (; i
< mp
->n_regions
&& end
> rp
->address
; ++i
, ++rp
) {
78 if (must_exist
&& (start
< rs
|| end
> re
)) {
79 printk("mem_pieces_remove: bad overlap [%x,%x) with",
85 rp
->size
= start
- rs
;
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];
94 rp
[1].size
= re
- end
;
101 /* need to delete this entry */
102 for (j
= i
; j
< mp
->n_regions
- 1; ++j
)
103 mp
->regions
[j
] = mp
->regions
[j
+1];
113 mem_pieces_print(struct mem_pieces
*mp
)
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
);
124 mem_pieces_sort(struct mem_pieces
*mp
)
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
)
135 mp
->regions
[j
+1] = mp
->regions
[j
];
137 mp
->regions
[j
+1].address
= a
;
138 mp
->regions
[j
+1].size
= s
;
143 mem_pieces_coalesce(struct mem_pieces
*mp
)
145 unsigned long a
, s
, ns
;
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
;
158 mp
->regions
[d
].address
= a
;
159 mp
->regions
[d
].size
= s
;