2 * Procedures for maintaining information about logical memory blocks.
4 * Peter Bergner, IBM Corp. June 2001.
5 * Copyright (C) 2001 Peter Bergner.
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version
10 * 2 of the License, or (at your option) any later version.
16 #define LMB_ALLOC_ANYWHERE 0
18 void lmb_dump_all(struct lmb
*lmb
)
23 debug("lmb_dump_all:\n");
24 debug(" memory.cnt = 0x%lx\n", lmb
->memory
.cnt
);
25 debug(" memory.size = 0x%08x\n", lmb
->memory
.size
);
26 for (i
=0; i
< lmb
->memory
.cnt
;i
++) {
27 debug(" memory.reg[0x%x].base = 0x%08x\n", i
,
28 lmb
->memory
.region
[i
].base
);
29 debug(" .size = 0x%08x\n",
30 lmb
->memory
.region
[i
].size
);
33 debug("\n reserved.cnt = 0x%lx\n", lmb
->reserved
.cnt
);
34 debug(" reserved.size = 0x%08x\n", lmb
->reserved
.size
);
35 for (i
=0; i
< lmb
->reserved
.cnt
;i
++) {
36 debug(" reserved.reg[0x%x].base = 0x%08x\n", i
,
37 lmb
->reserved
.region
[i
].base
);
38 debug(" .size = 0x%08x\n",
39 lmb
->reserved
.region
[i
].size
);
44 static unsigned long lmb_addrs_overlap(ulong base1
,
45 ulong size1
, ulong base2
, ulong size2
)
47 return ((base1
< (base2
+size2
)) && (base2
< (base1
+size1
)));
50 static long lmb_addrs_adjacent(ulong base1
, ulong size1
,
51 ulong base2
, ulong size2
)
53 if (base2
== base1
+ size1
)
55 else if (base1
== base2
+ size2
)
61 static long lmb_regions_adjacent(struct lmb_region
*rgn
,
62 unsigned long r1
, unsigned long r2
)
64 ulong base1
= rgn
->region
[r1
].base
;
65 ulong size1
= rgn
->region
[r1
].size
;
66 ulong base2
= rgn
->region
[r2
].base
;
67 ulong size2
= rgn
->region
[r2
].size
;
69 return lmb_addrs_adjacent(base1
, size1
, base2
, size2
);
72 static void lmb_remove_region(struct lmb_region
*rgn
, unsigned long r
)
76 for (i
= r
; i
< rgn
->cnt
- 1; i
++) {
77 rgn
->region
[i
].base
= rgn
->region
[i
+ 1].base
;
78 rgn
->region
[i
].size
= rgn
->region
[i
+ 1].size
;
83 /* Assumption: base addr of region 1 < base addr of region 2 */
84 static void lmb_coalesce_regions(struct lmb_region
*rgn
,
85 unsigned long r1
, unsigned long r2
)
87 rgn
->region
[r1
].size
+= rgn
->region
[r2
].size
;
88 lmb_remove_region(rgn
, r2
);
91 void lmb_init(struct lmb
*lmb
)
93 /* Create a dummy zero size LMB which will get coalesced away later.
94 * This simplifies the lmb_add() code below...
96 lmb
->memory
.region
[0].base
= 0;
97 lmb
->memory
.region
[0].size
= 0;
102 lmb
->reserved
.region
[0].base
= 0;
103 lmb
->reserved
.region
[0].size
= 0;
104 lmb
->reserved
.cnt
= 1;
105 lmb
->reserved
.size
= 0;
108 /* This routine called with relocation disabled. */
109 static long lmb_add_region(struct lmb_region
*rgn
, ulong base
, ulong size
)
111 unsigned long coalesced
= 0;
114 if ((rgn
->cnt
== 1) && (rgn
->region
[0].size
== 0)) {
115 rgn
->region
[0].base
= base
;
116 rgn
->region
[0].size
= size
;
120 /* First try and coalesce this LMB with another. */
121 for (i
=0; i
< rgn
->cnt
; i
++) {
122 ulong rgnbase
= rgn
->region
[i
].base
;
123 ulong rgnsize
= rgn
->region
[i
].size
;
125 if ((rgnbase
== base
) && (rgnsize
== size
))
126 /* Already have this region, so we're done */
129 adjacent
= lmb_addrs_adjacent(base
,size
,rgnbase
,rgnsize
);
130 if ( adjacent
> 0 ) {
131 rgn
->region
[i
].base
-= size
;
132 rgn
->region
[i
].size
+= size
;
136 else if ( adjacent
< 0 ) {
137 rgn
->region
[i
].size
+= size
;
143 if ((i
< rgn
->cnt
-1) && lmb_regions_adjacent(rgn
, i
, i
+1) ) {
144 lmb_coalesce_regions(rgn
, i
, i
+1);
150 if (rgn
->cnt
>= MAX_LMB_REGIONS
)
153 /* Couldn't coalesce the LMB, so add it to the sorted table. */
154 for (i
= rgn
->cnt
-1; i
>= 0; i
--) {
155 if (base
< rgn
->region
[i
].base
) {
156 rgn
->region
[i
+1].base
= rgn
->region
[i
].base
;
157 rgn
->region
[i
+1].size
= rgn
->region
[i
].size
;
159 rgn
->region
[i
+1].base
= base
;
160 rgn
->region
[i
+1].size
= size
;
165 if (base
< rgn
->region
[0].base
) {
166 rgn
->region
[0].base
= base
;
167 rgn
->region
[0].size
= size
;
175 /* This routine may be called with relocation disabled. */
176 long lmb_add(struct lmb
*lmb
, ulong base
, ulong size
)
178 struct lmb_region
*_rgn
= &(lmb
->memory
);
180 return lmb_add_region(_rgn
, base
, size
);
183 long lmb_reserve(struct lmb
*lmb
, ulong base
, ulong size
)
185 struct lmb_region
*_rgn
= &(lmb
->reserved
);
187 return lmb_add_region(_rgn
, base
, size
);
190 long lmb_overlaps_region(struct lmb_region
*rgn
, ulong base
,
195 for (i
=0; i
< rgn
->cnt
; i
++) {
196 ulong rgnbase
= rgn
->region
[i
].base
;
197 ulong rgnsize
= rgn
->region
[i
].size
;
198 if ( lmb_addrs_overlap(base
,size
,rgnbase
,rgnsize
) ) {
203 return (i
< rgn
->cnt
) ? i
: -1;
206 ulong
lmb_alloc(struct lmb
*lmb
, ulong size
, ulong align
)
208 return lmb_alloc_base(lmb
, size
, align
, LMB_ALLOC_ANYWHERE
);
211 ulong
lmb_alloc_base(struct lmb
*lmb
, ulong size
, ulong align
, ulong max_addr
)
215 alloc
= __lmb_alloc_base(lmb
, size
, align
, max_addr
);
218 printf("ERROR: Failed to allocate 0x%lx bytes below 0x%lx.\n",
224 static ulong
lmb_align_down(ulong addr
, ulong size
)
226 return addr
& ~(size
- 1);
229 static ulong
lmb_align_up(ulong addr
, ulong size
)
231 return (addr
+ (size
- 1)) & ~(size
- 1);
234 ulong
__lmb_alloc_base(struct lmb
*lmb
, ulong size
, ulong align
, ulong max_addr
)
239 for (i
= lmb
->memory
.cnt
-1; i
>= 0; i
--) {
240 ulong lmbbase
= lmb
->memory
.region
[i
].base
;
241 ulong lmbsize
= lmb
->memory
.region
[i
].size
;
243 if (max_addr
== LMB_ALLOC_ANYWHERE
)
244 base
= lmb_align_down(lmbbase
+ lmbsize
- size
, align
);
245 else if (lmbbase
< max_addr
) {
246 base
= min(lmbbase
+ lmbsize
, max_addr
);
247 base
= lmb_align_down(base
- size
, align
);
251 while ((lmbbase
<= base
) &&
252 ((j
= lmb_overlaps_region(&(lmb
->reserved
), base
, size
)) >= 0) )
253 base
= lmb_align_down(lmb
->reserved
.region
[j
].base
- size
,
256 if ((base
!= 0) && (lmbbase
<= base
))
263 if (lmb_add_region(&(lmb
->reserved
), base
, lmb_align_up(size
, align
)) < 0)
269 int lmb_is_reserved(struct lmb
*lmb
, ulong addr
)
273 for (i
= 0; i
< lmb
->reserved
.cnt
; i
++) {
274 ulong upper
= lmb
->reserved
.region
[i
].base
+
275 lmb
->reserved
.region
[i
].size
- 1;
276 if ((addr
>= lmb
->reserved
.region
[i
].base
) && (addr
<= upper
))