Subversion Repositories HelenOS

Rev

Rev 2083 | Rev 2121 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2083 Rev 2089
1 
/*
 1 
/*
2 
 * Copyright (c) 2001-2005 Jakub Jermar
 2 
 * Copyright (c) 2001-2005 Jakub Jermar
3 
 * Copyright (c) 2005 Sergey Bondari
 3 
 * Copyright (c) 2005 Sergey Bondari
4 
 * All rights reserved.
 4 
 * All rights reserved.
5 
 *
 5 
 *
6 
 * Redistribution and use in source and binary forms, with or without
 6 
 * Redistribution and use in source and binary forms, with or without
7 
 * modification, are permitted provided that the following conditions
 7 
 * modification, are permitted provided that the following conditions
8 
 * are met:
 8 
 * are met:
9 
 *
 9 
 *
10 
 * - Redistributions of source code must retain the above copyright
 10 
 * - Redistributions of source code must retain the above copyright
11 
 *   notice, this list of conditions and the following disclaimer.
 11 
 *   notice, this list of conditions and the following disclaimer.
12 
 * - Redistributions in binary form must reproduce the above copyright
 12 
 * - Redistributions in binary form must reproduce the above copyright
13 
 *   notice, this list of conditions and the following disclaimer in the
 13 
 *   notice, this list of conditions and the following disclaimer in the
14 
 *   documentation and/or other materials provided with the distribution.
 14 
 *   documentation and/or other materials provided with the distribution.
15 
 * - The name of the author may not be used to endorse or promote products
 15 
 * - The name of the author may not be used to endorse or promote products
16 
 *   derived from this software without specific prior written permission.
 16 
 *   derived from this software without specific prior written permission.
17 
 *
 17 
 *
18 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 18 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 19 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 20 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 21 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 22 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 23 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 24 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 25 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 26 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 27 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 
 */
 28 
 */
29 
 
 29 
 
30 
/** @addtogroup genericmm
 30 
/** @addtogroup genericmm
31 
 * @{
 31 
 * @{
32 
 */
 32 
 */
33 
 
 33 
 
34 
/**
 34 
/**
35 
 * @file
 35 
 * @file
36 
 * @brief   Physical frame allocator.
 36 
 * @brief   Physical frame allocator.
37 
 *
 37 
 *
38 
 * This file contains the physical frame allocator and memory zone management.
 38 
 * This file contains the physical frame allocator and memory zone management.
39 
 * The frame allocator is built on top of the buddy allocator.
 39 
 * The frame allocator is built on top of the buddy allocator.
40 
 *
 40 
 *
41 
 * @see buddy.c
 41 
 * @see buddy.c
42 
 */
 42 
 */
43 
 
 43 
 
44 
/*
 44 
/*
45 
 * Locking order
 45 
 * Locking order
46 
 *
 46 
 *
47 
 * In order to access particular zone, the process must first lock
 47 
 * In order to access particular zone, the process must first lock
48 
 * the zones.lock, then lock the zone and then unlock the zones.lock.
 48 
 * the zones.lock, then lock the zone and then unlock the zones.lock.
49 
 * This insures, that we can fiddle with the zones in runtime without
 49 
 * This insures, that we can fiddle with the zones in runtime without
50 
 * affecting the processes.
 50 
 * affecting the processes.
51 
 *
 51 
 *
52 
 */
 52 
 */
53 
 
 53 
 
54 
#include <typedefs.h>
 - 
 
55 
#include <arch/types.h>
 54 
#include <arch/types.h>
56 
#include <mm/frame.h>
 55 
#include <mm/frame.h>
57 
#include <mm/as.h>
 56 
#include <mm/as.h>
58 
#include <panic.h>
 57 
#include <panic.h>
59 
#include <debug.h>
 58 
#include <debug.h>
60 
#include <adt/list.h>
 59 
#include <adt/list.h>
61 
#include <synch/spinlock.h>
 60 
#include <synch/spinlock.h>
62 
#include <arch/asm.h>
 61 
#include <arch/asm.h>
63 
#include <arch.h>
 62 
#include <arch.h>
64 
#include <print.h>
 63 
#include <print.h>
65 
#include <align.h>
 64 
#include <align.h>
66 
#include <mm/slab.h>
 65 
#include <mm/slab.h>
67 
#include <bitops.h>
 66 
#include <bitops.h>
68 
#include <macros.h>
 67 
#include <macros.h>
69 
 
 68 
 
70 
typedef struct {
 69 
typedef struct {
71 
    count_t refcount;   /**< tracking of shared frames  */
 70 
    count_t refcount;   /**< tracking of shared frames  */
72 
    uint8_t buddy_order;    /**< buddy system block order */
 71 
    uint8_t buddy_order;    /**< buddy system block order */
73 
    link_t buddy_link;  /**< link to the next free block inside one order */
 72 
    link_t buddy_link;  /**< link to the next free block inside one order */
74 
    void *parent;           /**< If allocated by slab, this points there */
 73 
    void *parent;           /**< If allocated by slab, this points there */
75 
} frame_t;
 74 
} frame_t;
76 
 
 75 
 
77 
typedef struct {
 76 
typedef struct {
78 
    SPINLOCK_DECLARE(lock); /**< this lock protects everything below */
 77 
    SPINLOCK_DECLARE(lock); /**< this lock protects everything below */
79 
    pfn_t base;     /**< frame_no of the first frame in the frames array */
 78 
    pfn_t base;     /**< frame_no of the first frame in the frames array */
80 
    count_t count;          /**< Size of zone */
 79 
    count_t count;          /**< Size of zone */
81 
 
 80 
 
82 
    frame_t *frames;    /**< array of frame_t structures in this zone */
 81 
    frame_t *frames;    /**< array of frame_t structures in this zone */
83 
    count_t free_count; /**< number of free frame_t structures */
 82 
    count_t free_count; /**< number of free frame_t structures */
84 
    count_t busy_count; /**< number of busy frame_t structures */
 83 
    count_t busy_count; /**< number of busy frame_t structures */
85 
   
 84 
   
86 
    buddy_system_t *buddy_system; /**< buddy system for the zone */
 85 
    buddy_system_t *buddy_system; /**< buddy system for the zone */
87 
    int flags;
 86 
    int flags;
88 
} zone_t;
 87 
} zone_t;
89 
 
 88 
 
90 
/*
 89 
/*
91 
 * The zoneinfo.lock must be locked when accessing zoneinfo structure.
 90 
 * The zoneinfo.lock must be locked when accessing zoneinfo structure.
92 
 * Some of the attributes in zone_t structures are 'read-only'
 91 
 * Some of the attributes in zone_t structures are 'read-only'
93 
 */
 92 
 */
94 
 
 93 
 
95 
struct {
 94 
struct {
96 
    SPINLOCK_DECLARE(lock);
 95 
    SPINLOCK_DECLARE(lock);
97 
    int count;
 96 
    int count;
98 
    zone_t *info[ZONES_MAX];
 97 
    zone_t *info[ZONES_MAX];
99 
} zones;
 98 
} zones;
100 
 
 99 
 
101 
 
 100 
 
102 
/*********************************/
 101 
/*********************************/
103 
/* Helper functions */
 102 
/* Helper functions */
104 
static inline index_t frame_index(zone_t *zone, frame_t *frame)
 103 
static inline index_t frame_index(zone_t *zone, frame_t *frame)
105 
{
 104 
{
106 
    return (index_t)(frame - zone->frames);
 105 
    return (index_t)(frame - zone->frames);
107 
}
 106 
}
108 
static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
 107 
static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
109 
{
 108 
{
110 
    return (index_t)(frame - zone->frames) + zone->base;
 109 
    return (index_t)(frame - zone->frames) + zone->base;
111 
}
 110 
}
112 
static inline int frame_index_valid(zone_t *zone, index_t index)
 111 
static inline int frame_index_valid(zone_t *zone, index_t index)
113 
{
 112 
{
114 
    return index >= 0 && index < zone->count;
 113 
    return index >= 0 && index < zone->count;
115 
}
 114 
}
116 
 
 115 
 
117 
/** Compute pfn_t from frame_t pointer & zone pointer */
 116 
/** Compute pfn_t from frame_t pointer & zone pointer */
118 
static index_t make_frame_index(zone_t *zone, frame_t *frame)
 117 
static index_t make_frame_index(zone_t *zone, frame_t *frame)
119 
{
 118 
{
120 
    return frame - zone->frames;
 119 
    return frame - zone->frames;
121 
}
 120 
}
122 
 
 121 
 
123 
/** Initialize frame structure
 122 
/** Initialize frame structure
124 
 *
 123 
 *
125 
 * Initialize frame structure.
 124 
 * Initialize frame structure.
126 
 *
 125 
 *
127 
 * @param frame Frame structure to be initialized.
 126 
 * @param frame Frame structure to be initialized.
128 
 */
 127 
 */
129 
static void frame_initialize(frame_t *frame)
 128 
static void frame_initialize(frame_t *frame)
130 
{
 129 
{
131 
    frame->refcount = 1;
 130 
    frame->refcount = 1;
132 
    frame->buddy_order = 0;
 131 
    frame->buddy_order = 0;
133 
}
 132 
}
134 
 
 133 
 
135 
/*************************************/
 134 
/*************************************/
136 
/* Zoneinfo functions */
 135 
/* Zoneinfo functions */
137 
 
 136 
 
138 
/**
 137 
/**
139 
 * Insert-sort zone into zones list
 138 
 * Insert-sort zone into zones list
140 
 *
 139 
 *
141 
 * @param newzone New zone to be inserted into zone list
 140 
 * @param newzone New zone to be inserted into zone list
142 
 * @return zone number on success, -1 on error
 141 
 * @return zone number on success, -1 on error
143 
 */
 142 
 */
144 
static int zones_add_zone(zone_t *newzone)
 143 
static int zones_add_zone(zone_t *newzone)
145 
{
 144 
{
146 
    int i,j;
 145 
    int i,j;
147 
    ipl_t ipl;
 146 
    ipl_t ipl;
148 
    zone_t *z;
 147 
    zone_t *z;
149 
 
 148 
 
150 
    ipl = interrupts_disable();
 149 
    ipl = interrupts_disable();
151 
    spinlock_lock(&zones.lock);
 150 
    spinlock_lock(&zones.lock);
152 
    /* Try to merge */
 151 
    /* Try to merge */
153 
    if (zones.count + 1 == ZONES_MAX)
 152 
    if (zones.count + 1 == ZONES_MAX)
154 
        panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
 153 
        panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
155 
    for (i = 0; i < zones.count; i++) {
 154 
    for (i = 0; i < zones.count; i++) {
156 
        /* Check for overflow */
 155 
        /* Check for overflow */
157 
        z = zones.info[i];
 156 
        z = zones.info[i];
158 
        if (overlaps(newzone->base,newzone->count,
 157 
        if (overlaps(newzone->base,newzone->count,
159 
                 z->base, z->count)) {
 158 
                 z->base, z->count)) {
160 
            printf("Zones overlap!\n");
 159 
            printf("Zones overlap!\n");
161 
            return -1;
 160 
            return -1;
162 
        }
 161 
        }
163 
        if (newzone->base < z->base)
 162 
        if (newzone->base < z->base)
164 
            break;
 163 
            break;
165 
    }
 164 
    }
166 
    /* Move other zones up */
 165 
    /* Move other zones up */
167 
    for (j = i;j < zones.count; j++)
 166 
    for (j = i;j < zones.count; j++)
168 
        zones.info[j + 1] = zones.info[j];
 167 
        zones.info[j + 1] = zones.info[j];
169 
    zones.info[i] = newzone;
 168 
    zones.info[i] = newzone;
170 
    zones.count++;
 169 
    zones.count++;
171 
    spinlock_unlock(&zones.lock);
 170 
    spinlock_unlock(&zones.lock);
172 
    interrupts_restore(ipl);
 171 
    interrupts_restore(ipl);
173 
 
 172 
 
174 
    return i;
 173 
    return i;
175 
}
 174 
}
176 
 
 175 
 
177 
/**
 176 
/**
178 
 * Try to find a zone where can we find the frame
 177 
 * Try to find a zone where can we find the frame
179 
 
 178 
 
180 
 * Assume interrupts are disabled.
 179 
 * Assume interrupts are disabled.
181 
 
 180 
 
182 
 * @param frame Frame number contained in zone
 181 
 * @param frame Frame number contained in zone
183 
 * @param pzone If not null, it is used as zone hint. Zone index
 182 
 * @param pzone If not null, it is used as zone hint. Zone index
184 
 *              is filled into the variable on success.
 183 
 *              is filled into the variable on success.
185 
 * @return Pointer to locked zone containing frame
 184 
 * @return Pointer to locked zone containing frame
186 
 */
 185 
 */
187 
static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
 186 
static zone_t * find_zone_and_lock(pfn_t frame, int *pzone)
188 
{
 187 
{
189 
    int i;
 188 
    int i;
190 
    int hint = pzone ? *pzone : 0;
 189 
    int hint = pzone ? *pzone : 0;
191 
    zone_t *z;
 190 
    zone_t *z;
192 
   
 191 
   
193 
    spinlock_lock(&zones.lock);
 192 
    spinlock_lock(&zones.lock);
194 
 
 193 
 
195 
    if (hint >= zones.count || hint < 0)
 194 
    if (hint >= zones.count || hint < 0)
196 
        hint = 0;
 195 
        hint = 0;
197 
   
 196 
   
198 
    i = hint;
 197 
    i = hint;
199 
    do {
 198 
    do {
200 
        z = zones.info[i];
 199 
        z = zones.info[i];
201 
        spinlock_lock(&z->lock);
 200 
        spinlock_lock(&z->lock);
202 
        if (z->base <= frame && z->base + z->count > frame) {
 201 
        if (z->base <= frame && z->base + z->count > frame) {
203 
            spinlock_unlock(&zones.lock); /* Unlock the global lock */
 202 
            spinlock_unlock(&zones.lock); /* Unlock the global lock */
204 
            if (pzone)
 203 
            if (pzone)
205 
                *pzone = i;
 204 
                *pzone = i;
206 
            return z;
 205 
            return z;
207 
        }
 206 
        }
208 
        spinlock_unlock(&z->lock);
 207 
        spinlock_unlock(&z->lock);
209 
 
 208 
 
210 
        i++;
 209 
        i++;
211 
        if (i >= zones.count)
 210 
        if (i >= zones.count)
212 
            i = 0;
 211 
            i = 0;
213 
    } while(i != hint);
 212 
    } while(i != hint);
214 
 
 213 
 
215 
    spinlock_unlock(&zones.lock);
 214 
    spinlock_unlock(&zones.lock);
216 
    return NULL;
 215 
    return NULL;
217 
}
 216 
}
218 
 
 217 
 
219 
/** @return True if zone can allocate specified order */
 218 
/** @return True if zone can allocate specified order */
220 
static int zone_can_alloc(zone_t *z, uint8_t order)
 219 
static int zone_can_alloc(zone_t *z, uint8_t order)
221 
{
 220 
{
222 
    return buddy_system_can_alloc(z->buddy_system, order);
 221 
    return buddy_system_can_alloc(z->buddy_system, order);
223 
}
 222 
}
224 
 
 223 
 
225 
/** Find and lock zone that can allocate order frames.
 224 
/** Find and lock zone that can allocate order frames.
226 
 *
 225 
 *
227 
 * Assume interrupts are disabled.
 226 
 * Assume interrupts are disabled.
228 
 *
 227 
 *
229 
 * @param order Size (2^order) of free space we are trying to find
 228 
 * @param order Size (2^order) of free space we are trying to find
230 
 * @param pzone Pointer to preferred zone or NULL, on return contains zone number
 229 
 * @param pzone Pointer to preferred zone or NULL, on return contains zone number
231 
 */
 230 
 */
232 
static zone_t * find_free_zone_and_lock(uint8_t order, int *pzone)
 231 
static zone_t * find_free_zone_and_lock(uint8_t order, int *pzone)
233 
{
 232 
{
234 
    int i;
 233 
    int i;
235 
    zone_t *z;
 234 
    zone_t *z;
236 
    int hint = pzone ? *pzone : 0;
 235 
    int hint = pzone ? *pzone : 0;
237 
   
 236 
   
238 
    spinlock_lock(&zones.lock);
 237 
    spinlock_lock(&zones.lock);
239 
    if (hint >= zones.count)
 238 
    if (hint >= zones.count)
240 
        hint = 0;
 239 
        hint = 0;
241 
    i = hint;
 240 
    i = hint;
242 
    do {
 241 
    do {
243 
        z = zones.info[i];
 242 
        z = zones.info[i];
244 
       
 243 
       
245 
        spinlock_lock(&z->lock);
 244 
        spinlock_lock(&z->lock);
246 
 
 245 
 
247 
        /* Check if the zone has 2^order frames area available  */
 246 
        /* Check if the zone has 2^order frames area available  */
248 
        if (zone_can_alloc(z, order)) {
 247 
        if (zone_can_alloc(z, order)) {
249 
            spinlock_unlock(&zones.lock);
 248 
            spinlock_unlock(&zones.lock);
250 
            if (pzone)
 249 
            if (pzone)
251 
                *pzone = i;
 250 
                *pzone = i;
252 
            return z;
 251 
            return z;
253 
        }
 252 
        }
254 
        spinlock_unlock(&z->lock);
 253 
        spinlock_unlock(&z->lock);
255 
        if (++i >= zones.count)
 254 
        if (++i >= zones.count)
256 
            i = 0;
 255 
            i = 0;
257 
    } while(i != hint);
 256 
    } while(i != hint);
258 
    spinlock_unlock(&zones.lock);
 257 
    spinlock_unlock(&zones.lock);
259 
    return NULL;
 258 
    return NULL;
260 
}
 259 
}
261 
 
 260 
 
262 
/**************************/
 261 
/**************************/
263 
/* Buddy system functions */
 262 
/* Buddy system functions */
264 
/**************************/
 263 
/**************************/
265 
 
 264 
 
266 
/** Buddy system find_block implementation
 265 
/** Buddy system find_block implementation
267 
 *
 266 
 *
268 
 * Find block that is parent of current list.
 267 
 * Find block that is parent of current list.
269 
 * That means go to lower addresses, until such block is found
 268 
 * That means go to lower addresses, until such block is found
270 
 *
 269 
 *
271 
 * @param order - Order of parent must be different then this parameter!!
 270 
 * @param order - Order of parent must be different then this parameter!!
272 
 */
 271 
 */
273 
static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
 272 
static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
274 
                     uint8_t order)
 273 
                     uint8_t order)
275 
{
 274 
{
276 
    frame_t * frame;
 275 
    frame_t * frame;
277 
    zone_t * zone;
 276 
    zone_t * zone;
278 
    index_t index;
 277 
    index_t index;
279 
   
 278 
   
280 
    frame = list_get_instance(child, frame_t, buddy_link);
 279 
    frame = list_get_instance(child, frame_t, buddy_link);
281 
    zone = (zone_t *) b->data;
 280 
    zone = (zone_t *) b->data;
282 
 
 281 
 
283 
    index = frame_index(zone, frame);
 282 
    index = frame_index(zone, frame);
284 
    do {
 283 
    do {
285 
        if (zone->frames[index].buddy_order != order) {
 284 
        if (zone->frames[index].buddy_order != order) {
286 
            return &zone->frames[index].buddy_link;
 285 
            return &zone->frames[index].buddy_link;
287 
        }
 286 
        }
288 
    } while(index-- > 0);
 287 
    } while(index-- > 0);
289 
    return NULL;
 288 
    return NULL;
290 
}
 289 
}
291 
 
 290 
 
292 
static void zone_buddy_print_id(buddy_system_t *b, link_t *block)
 291 
static void zone_buddy_print_id(buddy_system_t *b, link_t *block)
293 
{
 292 
{
294 
    frame_t * frame;
 293 
    frame_t * frame;
295 
    zone_t * zone;
 294 
    zone_t * zone;
296 
    index_t index;
 295 
    index_t index;
297 
 
 296 
 
298 
    frame = list_get_instance(block, frame_t, buddy_link);
 297 
    frame = list_get_instance(block, frame_t, buddy_link);
299 
    zone = (zone_t *) b->data;
 298 
    zone = (zone_t *) b->data;
300 
    index = frame_index(zone, frame);
 299 
    index = frame_index(zone, frame);
301 
    printf("%zd", index);
 300 
    printf("%zd", index);
302 
}                    
 301 
}                    
303 
 
 302 
 
304 
/** Buddy system find_buddy implementation
 303 
/** Buddy system find_buddy implementation
305 
 *
 304 
 *
306 
 * @param b Buddy system.
 305 
 * @param b Buddy system.
307 
 * @param block Block for which buddy should be found
 306 
 * @param block Block for which buddy should be found
308 
 *
 307 
 *
309 
 * @return Buddy for given block if found
 308 
 * @return Buddy for given block if found
310 
 */
 309 
 */
311 
static link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block)
 310 
static link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block)
312 
{
 311 
{
313 
    frame_t * frame;
 312 
    frame_t * frame;
314 
    zone_t * zone;
 313 
    zone_t * zone;
315 
    index_t index;
 314 
    index_t index;
316 
    bool is_left, is_right;
 315 
    bool is_left, is_right;
317 
 
 316 
 
318 
    frame = list_get_instance(block, frame_t, buddy_link);
 317 
    frame = list_get_instance(block, frame_t, buddy_link);
319 
    zone = (zone_t *) b->data;
 318 
    zone = (zone_t *) b->data;
320 
    ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
 319 
    ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
321 
   
 320 
   
322 
    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
 321 
    is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
323 
    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
 322 
    is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
324 
 
 323 
 
325 
    ASSERT(is_left ^ is_right);
 324 
    ASSERT(is_left ^ is_right);
326 
    if (is_left) {
 325 
    if (is_left) {
327 
        index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
 326 
        index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
328 
    } else {    /* if (is_right) */
 327 
    } else {    /* if (is_right) */
329 
        index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
 328 
        index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
330 
    }
 329 
    }
331 
   
 330 
   
332 
    if (frame_index_valid(zone, index)) {
 331 
    if (frame_index_valid(zone, index)) {
333 
        if (zone->frames[index].buddy_order == frame->buddy_order &&
 332 
        if (zone->frames[index].buddy_order == frame->buddy_order &&
334 
            zone->frames[index].refcount == 0) {
 333 
            zone->frames[index].refcount == 0) {
335 
            return &zone->frames[index].buddy_link;
 334 
            return &zone->frames[index].buddy_link;
336 
        }
 335 
        }
337 
    }
 336 
    }
338 
 
 337 
 
339 
    return NULL;   
 338 
    return NULL;   
340 
}
 339 
}
341 
 
 340 
 
342 
/** Buddy system bisect implementation
 341 
/** Buddy system bisect implementation
343 
 *
 342 
 *
344 
 * @param b Buddy system.
 343 
 * @param b Buddy system.
345 
 * @param block Block to bisect
 344 
 * @param block Block to bisect
346 
 *
 345 
 *
347 
 * @return right block
 346 
 * @return right block
348 
 */
 347 
 */
349 
static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
 348 
static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
350 
    frame_t * frame_l, * frame_r;
 349 
    frame_t * frame_l, * frame_r;
351 
 
 350 
 
352 
    frame_l = list_get_instance(block, frame_t, buddy_link);
 351 
    frame_l = list_get_instance(block, frame_t, buddy_link);
353 
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
 352 
    frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
354 
   
 353 
   
355 
    return &frame_r->buddy_link;
 354 
    return &frame_r->buddy_link;
356 
}
 355 
}
357 
 
 356 
 
358 
/** Buddy system coalesce implementation
 357 
/** Buddy system coalesce implementation
359 
 *
 358 
 *
360 
 * @param b Buddy system.
 359 
 * @param b Buddy system.
361 
 * @param block_1 First block
 360 
 * @param block_1 First block
362 
 * @param block_2 First block's buddy
 361 
 * @param block_2 First block's buddy
363 
 *
 362 
 *
364 
 * @return Coalesced block (actually block that represents lower address)
 363 
 * @return Coalesced block (actually block that represents lower address)
365 
 */
 364 
 */
366 
static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
 365 
static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
367 
                    link_t * block_2)
 366 
                    link_t * block_2)
368 
{
 367 
{
369 
    frame_t *frame1, *frame2;
 368 
    frame_t *frame1, *frame2;
370 
   
 369 
   
371 
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
 370 
    frame1 = list_get_instance(block_1, frame_t, buddy_link);
372 
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
 371 
    frame2 = list_get_instance(block_2, frame_t, buddy_link);
373 
   
 372 
   
374 
    return frame1 < frame2 ? block_1 : block_2;
 373 
    return frame1 < frame2 ? block_1 : block_2;
375 
}
 374 
}
376 
 
 375 
 
377 
/** Buddy system set_order implementation
 376 
/** Buddy system set_order implementation
378 
 *
 377 
 *
379 
 * @param b Buddy system.
 378 
 * @param b Buddy system.
380 
 * @param block Buddy system block
 379 
 * @param block Buddy system block
381 
 * @param order Order to set
 380 
 * @param order Order to set
382 
 */
 381 
 */
383 
static void zone_buddy_set_order(buddy_system_t *b, link_t * block, uint8_t order) {
 382 
static void zone_buddy_set_order(buddy_system_t *b, link_t * block, uint8_t order) {
384 
    frame_t * frame;
 383 
    frame_t * frame;
385 
    frame = list_get_instance(block, frame_t, buddy_link);
 384 
    frame = list_get_instance(block, frame_t, buddy_link);
386 
    frame->buddy_order = order;
 385 
    frame->buddy_order = order;
387 
}
 386 
}
388 
 
 387 
 
389 
/** Buddy system get_order implementation
 388 
/** Buddy system get_order implementation
390 
 *
 389 
 *
391 
 * @param b Buddy system.
 390 
 * @param b Buddy system.
392 
 * @param block Buddy system block
 391 
 * @param block Buddy system block
393 
 *
 392 
 *
394 
 * @return Order of block
 393 
 * @return Order of block
395 
 */
 394 
 */
396 
static uint8_t zone_buddy_get_order(buddy_system_t *b, link_t * block) {
 395 
static uint8_t zone_buddy_get_order(buddy_system_t *b, link_t * block) {
397 
    frame_t * frame;
 396 
    frame_t * frame;
398 
    frame = list_get_instance(block, frame_t, buddy_link);
 397 
    frame = list_get_instance(block, frame_t, buddy_link);
399 
    return frame->buddy_order;
 398 
    return frame->buddy_order;
400 
}
 399 
}
401 
 
 400 
 
402 
/** Buddy system mark_busy implementation
 401 
/** Buddy system mark_busy implementation
403 
 *
 402 
 *
404 
 * @param b Buddy system
 403 
 * @param b Buddy system
405 
 * @param block Buddy system block
 404 
 * @param block Buddy system block
406 
 *
 405 
 *
407 
 */
 406 
 */
408 
static void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
 407 
static void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
409 
    frame_t * frame;
 408 
    frame_t * frame;
410 
 
 409 
 
411 
    frame = list_get_instance(block, frame_t, buddy_link);
 410 
    frame = list_get_instance(block, frame_t, buddy_link);
412 
    frame->refcount = 1;
 411 
    frame->refcount = 1;
413 
}
 412 
}
414 
 
 413 
 
415 
/** Buddy system mark_available implementation
 414 
/** Buddy system mark_available implementation
416 
 *
 415 
 *
417 
 * @param b Buddy system
 416 
 * @param b Buddy system
418 
 * @param block Buddy system block
 417 
 * @param block Buddy system block
419 
 *
 418 
 *
420 
 */
 419 
 */
421 
static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
 420 
static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
422 
    frame_t * frame;
 421 
    frame_t * frame;
423 
    frame = list_get_instance(block, frame_t, buddy_link);
 422 
    frame = list_get_instance(block, frame_t, buddy_link);
424 
    frame->refcount = 0;
 423 
    frame->refcount = 0;
425 
}
 424 
}
426 
 
 425 
 
427 
static buddy_system_operations_t zone_buddy_system_operations = {
 426 
static buddy_system_operations_t zone_buddy_system_operations = {
428 
    .find_buddy = zone_buddy_find_buddy,
 427 
    .find_buddy = zone_buddy_find_buddy,
429 
    .bisect = zone_buddy_bisect,
 428 
    .bisect = zone_buddy_bisect,
430 
    .coalesce = zone_buddy_coalesce,
 429 
    .coalesce = zone_buddy_coalesce,
431 
    .set_order = zone_buddy_set_order,
 430 
    .set_order = zone_buddy_set_order,
432 
    .get_order = zone_buddy_get_order,
 431 
    .get_order = zone_buddy_get_order,
433 
    .mark_busy = zone_buddy_mark_busy,
 432 
    .mark_busy = zone_buddy_mark_busy,
434 
    .mark_available = zone_buddy_mark_available,
 433 
    .mark_available = zone_buddy_mark_available,
435 
    .find_block = zone_buddy_find_block,
 434 
    .find_block = zone_buddy_find_block,
436 
    .print_id = zone_buddy_print_id
 435 
    .print_id = zone_buddy_print_id
437 
};
 436 
};
438 
 
 437 
 
439 
/******************/
 438 
/******************/
440 
/* Zone functions */
 439 
/* Zone functions */
441 
/******************/
 440 
/******************/
442 
 
 441 
 
443 
/** Allocate frame in particular zone
 442 
/** Allocate frame in particular zone
444 
 *
 443 
 *
445 
 * Assume zone is locked
 444 
 * Assume zone is locked
446 
 * Panics if allocation is impossible.
 445 
 * Panics if allocation is impossible.
447 
 *
 446 
 *
448 
 * @param zone  Zone to allocate from.
 447 
 * @param zone  Zone to allocate from.
449 
 * @param order Allocate exactly 2^order frames.
 448 
 * @param order Allocate exactly 2^order frames.
450 
 *
 449 
 *
451 
 * @return Frame index in zone
 450 
 * @return Frame index in zone
452 
 *
 451 
 *
453 
 */
 452 
 */
454 
static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
 453 
static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
455 
{
 454 
{
456 
    pfn_t v;
 455 
    pfn_t v;
457 
    link_t *tmp;
 456 
    link_t *tmp;
458 
    frame_t *frame;
 457 
    frame_t *frame;
459 
 
 458 
 
460 
    /* Allocate frames from zone buddy system */
 459 
    /* Allocate frames from zone buddy system */
461 
    tmp = buddy_system_alloc(zone->buddy_system, order);
 460 
    tmp = buddy_system_alloc(zone->buddy_system, order);
462 
   
 461 
   
463 
    ASSERT(tmp);
 462 
    ASSERT(tmp);
464 
   
 463 
   
465 
    /* Update zone information. */
 464 
    /* Update zone information. */
466 
    zone->free_count -= (1 << order);
 465 
    zone->free_count -= (1 << order);
467 
    zone->busy_count += (1 << order);
 466 
    zone->busy_count += (1 << order);
468 
 
 467 
 
469 
    /* Frame will be actually a first frame of the block. */
 468 
    /* Frame will be actually a first frame of the block. */
470 
    frame = list_get_instance(tmp, frame_t, buddy_link);
 469 
    frame = list_get_instance(tmp, frame_t, buddy_link);
471 
   
 470 
   
472 
    /* get frame address */
 471 
    /* get frame address */
473 
    v = make_frame_index(zone, frame);
 472 
    v = make_frame_index(zone, frame);
474 
    return v;
 473 
    return v;
475 
}
 474 
}
476 
 
 475 
 
477 
/** Free frame from zone
 476 
/** Free frame from zone
478 
 *
 477 
 *
479 
 * Assume zone is locked
 478 
 * Assume zone is locked
480 
 *
 479 
 *
481 
 * @param zone Pointer to zone from which the frame is to be freed
 480 
 * @param zone Pointer to zone from which the frame is to be freed
482 
 * @param frame_idx Frame index relative to zone
 481 
 * @param frame_idx Frame index relative to zone
483 
 */
 482 
 */
484 
static void zone_frame_free(zone_t *zone, index_t frame_idx)
 483 
static void zone_frame_free(zone_t *zone, index_t frame_idx)
485 
{
 484 
{
486 
    frame_t *frame;
 485 
    frame_t *frame;
487 
    uint8_t order;
 486 
    uint8_t order;
488 
 
 487 
 
489 
    frame = &zone->frames[frame_idx];
 488 
    frame = &zone->frames[frame_idx];
490 
   
 489 
   
491 
    /* remember frame order */
 490 
    /* remember frame order */
492 
    order = frame->buddy_order;
 491 
    order = frame->buddy_order;
493 
 
 492 
 
494 
    ASSERT(frame->refcount);
 493 
    ASSERT(frame->refcount);
495 
 
 494 
 
496 
    if (!--frame->refcount) {
 495 
    if (!--frame->refcount) {
497 
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
 496 
        buddy_system_free(zone->buddy_system, &frame->buddy_link);
498 
   
 497 
   
499 
        /* Update zone information. */
 498 
        /* Update zone information. */
500 
        zone->free_count += (1 << order);
 499 
        zone->free_count += (1 << order);
501 
        zone->busy_count -= (1 << order);
 500 
        zone->busy_count -= (1 << order);
502 
    }
 501 
    }
503 
}
 502 
}
504 
 
 503 
 
505 
/** Return frame from zone */
 504 
/** Return frame from zone */
506 
static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
 505 
static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
507 
{
 506 
{
508 
    ASSERT(frame_idx < zone->count);
 507 
    ASSERT(frame_idx < zone->count);
509 
    return &zone->frames[frame_idx];
 508 
    return &zone->frames[frame_idx];
510 
}
 509 
}
511 
 
 510 
 
512 
/** Mark frame in zone unavailable to allocation */
 511 
/** Mark frame in zone unavailable to allocation */
513 
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
 512 
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
514 
{
 513 
{
515 
    frame_t *frame;
 514 
    frame_t *frame;
516 
    link_t *link;
 515 
    link_t *link;
517 
 
 516 
 
518 
    frame = zone_get_frame(zone, frame_idx);
 517 
    frame = zone_get_frame(zone, frame_idx);
519 
    if (frame->refcount)
 518 
    if (frame->refcount)
520 
        return;
 519 
        return;
521 
    link = buddy_system_alloc_block(zone->buddy_system,
 520 
    link = buddy_system_alloc_block(zone->buddy_system,
522 
                    &frame->buddy_link);
 521 
                    &frame->buddy_link);
523 
    ASSERT(link);
 522 
    ASSERT(link);
524 
    zone->free_count--;
 523 
    zone->free_count--;
525 
}
 524 
}
526 
 
 525 
 
527 
/**
 526 
/**
528 
 * Join 2 zones
 527 
 * Join 2 zones
529 
 *
 528 
 *
530 
 * Expect zone_t *z to point to space at least zone_conf_size large
 529 
 * Expect zone_t *z to point to space at least zone_conf_size large
531 
 *
 530 
 *
532 
 * Assume z1 & z2 are locked
 531 
 * Assume z1 & z2 are locked
533 
 *
 532 
 *
534 
 * @param z Target zone structure pointer
 533 
 * @param z Target zone structure pointer
535 
 * @param z1 Zone to merge
 534 
 * @param z1 Zone to merge
536 
 * @param z2 Zone to merge
 535 
 * @param z2 Zone to merge
537 
 */
 536 
 */
538 
static void _zone_merge(zone_t *z, zone_t *z1, zone_t *z2)
 537 
static void _zone_merge(zone_t *z, zone_t *z1, zone_t *z2)
539 
{
 538 
{
540 
    uint8_t max_order;
 539 
    uint8_t max_order;
541 
    int i, z2idx;
 540 
    int i, z2idx;
542 
    pfn_t frame_idx;
 541 
    pfn_t frame_idx;
543 
    frame_t *frame;
 542 
    frame_t *frame;
544 
 
 543 
 
545 
    ASSERT(!overlaps(z1->base,z1->count,z2->base,z2->count));
 544 
    ASSERT(!overlaps(z1->base,z1->count,z2->base,z2->count));
546 
    ASSERT(z1->base < z2->base);
 545 
    ASSERT(z1->base < z2->base);
547 
 
 546 
 
548 
    spinlock_initialize(&z->lock, "zone_lock");
 547 
    spinlock_initialize(&z->lock, "zone_lock");
549 
    z->base = z1->base;
 548 
    z->base = z1->base;
550 
    z->count = z2->base+z2->count - z1->base;
 549 
    z->count = z2->base+z2->count - z1->base;
551 
    z->flags = z1->flags & z2->flags;
 550 
    z->flags = z1->flags & z2->flags;
552 
 
 551 
 
553 
    z->free_count = z1->free_count + z2->free_count;
 552 
    z->free_count = z1->free_count + z2->free_count;
554 
    z->busy_count = z1->busy_count + z2->busy_count;
 553 
    z->busy_count = z1->busy_count + z2->busy_count;
555 
   
 554 
   
556 
    max_order = fnzb(z->count);
 555 
    max_order = fnzb(z->count);
557 
 
 556 
 
558 
    z->buddy_system = (buddy_system_t *)&z[1];
 557 
    z->buddy_system = (buddy_system_t *)&z[1];
559 
    buddy_system_create(z->buddy_system, max_order,
 558 
    buddy_system_create(z->buddy_system, max_order,
560 
                &zone_buddy_system_operations,
 559 
                &zone_buddy_system_operations,
561 
                (void *) z);
 560 
                (void *) z);
562 
 
 561 
 
563 
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
 562 
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
564 
    for (i = 0; i < z->count; i++) {
 563 
    for (i = 0; i < z->count; i++) {
565 
        /* This marks all frames busy */
 564 
        /* This marks all frames busy */
566 
        frame_initialize(&z->frames[i]);
 565 
        frame_initialize(&z->frames[i]);
567 
    }
 566 
    }
568 
    /* Copy frames from both zones to preserve full frame orders,
 567 
    /* Copy frames from both zones to preserve full frame orders,
569 
     * parents etc. Set all free frames with refcount=0 to 1, because
 568 
     * parents etc. Set all free frames with refcount=0 to 1, because
570 
     * we add all free frames to buddy allocator later again, clear
 569 
     * we add all free frames to buddy allocator later again, clear
571 
     * order to 0. Don't set busy frames with refcount=0, as they
 570 
     * order to 0. Don't set busy frames with refcount=0, as they
572 
     * will not be reallocated during merge and it would make later
 571 
     * will not be reallocated during merge and it would make later
573 
     * problems with allocation/free.
 572 
     * problems with allocation/free.
574 
     */
 573 
     */
575 
    for (i=0; i<z1->count; i++)
 574 
    for (i=0; i<z1->count; i++)
576 
        z->frames[i] = z1->frames[i];
 575 
        z->frames[i] = z1->frames[i];
577 
    for (i=0; i < z2->count; i++) {
 576 
    for (i=0; i < z2->count; i++) {
578 
        z2idx = i + (z2->base - z1->base);
 577 
        z2idx = i + (z2->base - z1->base);
579 
        z->frames[z2idx] = z2->frames[i];
 578 
        z->frames[z2idx] = z2->frames[i];
580 
    }
 579 
    }
581 
    i = 0;
 580 
    i = 0;
582 
    while (i < z->count) {
 581 
    while (i < z->count) {
583 
        if (z->frames[i].refcount) {
 582 
        if (z->frames[i].refcount) {
584 
            /* skip busy frames */
 583 
            /* skip busy frames */
585 
            i += 1 << z->frames[i].buddy_order;
 584 
            i += 1 << z->frames[i].buddy_order;
586 
        } else { /* Free frames, set refcount=1 */
 585 
        } else { /* Free frames, set refcount=1 */
587 
            /* All free frames have refcount=0, we need not
 586 
            /* All free frames have refcount=0, we need not
588 
             * to check the order */
 587 
             * to check the order */
589 
            z->frames[i].refcount = 1;
 588 
            z->frames[i].refcount = 1;
590 
            z->frames[i].buddy_order = 0;
 589 
            z->frames[i].buddy_order = 0;
591 
            i++;
 590 
            i++;
592 
        }
 591 
        }
593 
    }
 592 
    }
594 
    /* Add free blocks from the 2 original zones */
 593 
    /* Add free blocks from the 2 original zones */
595 
    while (zone_can_alloc(z1, 0)) {
 594 
    while (zone_can_alloc(z1, 0)) {
596 
        frame_idx = zone_frame_alloc(z1, 0);
 595 
        frame_idx = zone_frame_alloc(z1, 0);
597 
        frame = &z->frames[frame_idx];
 596 
        frame = &z->frames[frame_idx];
598 
        frame->refcount = 0;
 597 
        frame->refcount = 0;
599 
        buddy_system_free(z->buddy_system, &frame->buddy_link);
 598 
        buddy_system_free(z->buddy_system, &frame->buddy_link);
600 
    }
 599 
    }
601 
    while (zone_can_alloc(z2, 0)) {
 600 
    while (zone_can_alloc(z2, 0)) {
602 
        frame_idx = zone_frame_alloc(z2, 0);
 601 
        frame_idx = zone_frame_alloc(z2, 0);
603 
        frame = &z->frames[frame_idx + (z2->base-z1->base)];
 602 
        frame = &z->frames[frame_idx + (z2->base-z1->base)];
604 
        frame->refcount = 0;
 603 
        frame->refcount = 0;
605 
        buddy_system_free(z->buddy_system, &frame->buddy_link);
 604 
        buddy_system_free(z->buddy_system, &frame->buddy_link);
606 
    }
 605 
    }
607 
}
 606 
}
608 
 
 607 
 
609 
/** Return old configuration frames into the zone
 608 
/** Return old configuration frames into the zone
610 
 *
 609 
 *
611 
 * We have several cases
 610 
 * We have several cases
612 
 * - the conf. data is outside of zone -> exit, shall we call frame_free??
 611 
 * - the conf. data is outside of zone -> exit, shall we call frame_free??
613 
 * - the conf. data was created by zone_create or
 612 
 * - the conf. data was created by zone_create or
614 
 *   updated with reduce_region -> free every frame
 613 
 *   updated with reduce_region -> free every frame
615 
 *
 614 
 *
616 
 * @param newzone The actual zone where freeing should occur
 615 
 * @param newzone The actual zone where freeing should occur
617 
 * @param oldzone Pointer to old zone configuration data that should
 616 
 * @param oldzone Pointer to old zone configuration data that should
618 
 *                be freed from new zone
 617 
 *                be freed from new zone
619 
 */
 618 
 */
620 
static void return_config_frames(zone_t *newzone, zone_t *oldzone)
 619 
static void return_config_frames(zone_t *newzone, zone_t *oldzone)
621 
{
 620 
{
622 
    pfn_t pfn;
 621 
    pfn_t pfn;
623 
    frame_t *frame;
 622 
    frame_t *frame;
624 
    count_t cframes;
 623 
    count_t cframes;
625 
    int i;
 624 
    int i;
626 
 
 625 
 
627 
    pfn = ADDR2PFN((uintptr_t)KA2PA(oldzone));
 626 
    pfn = ADDR2PFN((uintptr_t)KA2PA(oldzone));
628 
    cframes = SIZE2FRAMES(zone_conf_size(oldzone->count));
 627 
    cframes = SIZE2FRAMES(zone_conf_size(oldzone->count));
629 
   
 628 
   
630 
    if (pfn < newzone->base || pfn >= newzone->base + newzone->count)
 629 
    if (pfn < newzone->base || pfn >= newzone->base + newzone->count)
631 
        return;
 630 
        return;
632 
 
 631 
 
633 
    frame = &newzone->frames[pfn - newzone->base];
 632 
    frame = &newzone->frames[pfn - newzone->base];
634 
    ASSERT(!frame->buddy_order);
 633 
    ASSERT(!frame->buddy_order);
635 
 
 634 
 
636 
    for (i=0; i < cframes; i++) {
 635 
    for (i=0; i < cframes; i++) {
637 
        newzone->busy_count++;
 636 
        newzone->busy_count++;
638 
        zone_frame_free(newzone, pfn+i-newzone->base);
 637 
        zone_frame_free(newzone, pfn+i-newzone->base);
639 
    }
 638 
    }
640 
}
 639 
}
641 
 
 640 
 
642 
/** Reduce allocated block to count of order 0 frames
 641 
/** Reduce allocated block to count of order 0 frames
643 
 *
 642 
 *
644 
 * The allocated block need 2^order frames of space. Reduce all frames
 643 
 * The allocated block need 2^order frames of space. Reduce all frames
645 
 * in block to order 0 and free the unneeded frames. This means, that
 644 
 * in block to order 0 and free the unneeded frames. This means, that
646 
 * when freeing the previously allocated block starting with frame_idx,
 645 
 * when freeing the previously allocated block starting with frame_idx,
647 
 * you have to free every frame.
 646 
 * you have to free every frame.
648 
 *
 647 
 *
649 
 * @param zone
 648 
 * @param zone
650 
 * @param frame_idx Index to block
 649 
 * @param frame_idx Index to block
651 
 * @param count Allocated space in block
 650 
 * @param count Allocated space in block
652 
 */
 651 
 */
653 
static void zone_reduce_region(zone_t *zone, pfn_t frame_idx, count_t count)
 652 
static void zone_reduce_region(zone_t *zone, pfn_t frame_idx, count_t count)
654 
{
 653 
{
655 
    count_t i;
 654 
    count_t i;
656 
    uint8_t order;
 655 
    uint8_t order;
657 
    frame_t *frame;
 656 
    frame_t *frame;
658 
   
 657 
   
659 
    ASSERT(frame_idx+count < zone->count);
 658 
    ASSERT(frame_idx+count < zone->count);
660 
 
 659 
 
661 
    order = zone->frames[frame_idx].buddy_order;
 660 
    order = zone->frames[frame_idx].buddy_order;
662 
    ASSERT((1 << order) >= count);
 661 
    ASSERT((1 << order) >= count);
663 
 
 662 
 
664 
    /* Reduce all blocks to order 0 */
 663 
    /* Reduce all blocks to order 0 */
665 
    for (i=0; i < (1 << order); i++) {
 664 
    for (i=0; i < (1 << order); i++) {
666 
        frame = &zone->frames[i + frame_idx];
 665 
        frame = &zone->frames[i + frame_idx];
667 
        frame->buddy_order = 0;
 666 
        frame->buddy_order = 0;
668 
        if (! frame->refcount)
 667 
        if (! frame->refcount)
669 
            frame->refcount = 1;
 668 
            frame->refcount = 1;
670 
        ASSERT(frame->refcount == 1);
 669 
        ASSERT(frame->refcount == 1);
671 
    }
 670 
    }
672 
    /* Free unneeded frames */
 671 
    /* Free unneeded frames */
673 
    for (i=count; i < (1 << order); i++) {
 672 
    for (i=count; i < (1 << order); i++) {
674 
        zone_frame_free(zone, i + frame_idx);
 673 
        zone_frame_free(zone, i + frame_idx);
675 
    }
 674 
    }
676 
}
 675 
}
677 
 
 676 
 
678 
/** Merge zones z1 and z2
 677 
/** Merge zones z1 and z2
679 
 *
 678 
 *
680 
 * - the zones must be 2 zones with no zone existing in between,
 679 
 * - the zones must be 2 zones with no zone existing in between,
681 
 *   which means that z2 = z1+1
 680 
 *   which means that z2 = z1+1
682 
 *
 681 
 *
683 
 * - When you create a new zone, the frame allocator configuration does
 682 
 * - When you create a new zone, the frame allocator configuration does
684 
 *   not to be 2^order size. Once the allocator is running it is no longer
 683 
 *   not to be 2^order size. Once the allocator is running it is no longer
685 
 *   possible, merged configuration data occupies more space :-/
 684 
 *   possible, merged configuration data occupies more space :-/
686 
 */
 685 
 */
687 
void zone_merge(int z1, int z2)
 686 
void zone_merge(int z1, int z2)
688 
{
 687 
{
689 
    ipl_t ipl;
 688 
    ipl_t ipl;
690 
    zone_t *zone1, *zone2, *newzone;
 689 
    zone_t *zone1, *zone2, *newzone;
691 
    int cframes;
 690 
    int cframes;
692 
    uint8_t order;
 691 
    uint8_t order;
693 
    int i;
 692 
    int i;
694 
    pfn_t pfn;
 693 
    pfn_t pfn;
695 
 
 694 
 
696 
    ipl = interrupts_disable();
 695 
    ipl = interrupts_disable();
697 
    spinlock_lock(&zones.lock);
 696 
    spinlock_lock(&zones.lock);
698 
 
 697 
 
699 
    if (z1 < 0 || z1 >= zones.count || z2 < 0 || z2 >= zones.count)
 698 
    if (z1 < 0 || z1 >= zones.count || z2 < 0 || z2 >= zones.count)
700 
        goto errout;
 699 
        goto errout;
701 
    /* We can join only 2 zones with none existing inbetween */
 700 
    /* We can join only 2 zones with none existing inbetween */
702 
    if (z2-z1 != 1)
 701 
    if (z2-z1 != 1)
703 
        goto errout;
 702 
        goto errout;
704 
 
 703 
 
705 
    zone1 = zones.info[z1];
 704 
    zone1 = zones.info[z1];
706 
    zone2 = zones.info[z2];
 705 
    zone2 = zones.info[z2];
707 
    spinlock_lock(&zone1->lock);
 706 
    spinlock_lock(&zone1->lock);
708 
    spinlock_lock(&zone2->lock);
 707 
    spinlock_lock(&zone2->lock);
709 
 
 708 
 
710 
    cframes = SIZE2FRAMES(zone_conf_size(zone2->base+zone2->count-zone1->base));
 709 
    cframes = SIZE2FRAMES(zone_conf_size(zone2->base+zone2->count-zone1->base));
711 
    if (cframes == 1)
 710 
    if (cframes == 1)
712 
        order = 0;
 711 
        order = 0;
713 
    else
 712 
    else
714 
        order = fnzb(cframes - 1) + 1;
 713 
        order = fnzb(cframes - 1) + 1;
715 
 
 714 
 
716 
    /* Allocate zonedata inside one of the zones */
 715 
    /* Allocate zonedata inside one of the zones */
717 
    if (zone_can_alloc(zone1, order))
 716 
    if (zone_can_alloc(zone1, order))
718 
        pfn = zone1->base + zone_frame_alloc(zone1, order);
 717 
        pfn = zone1->base + zone_frame_alloc(zone1, order);
719 
    else if (zone_can_alloc(zone2, order))
 718 
    else if (zone_can_alloc(zone2, order))
720 
        pfn = zone2->base + zone_frame_alloc(zone2, order);
 719 
        pfn = zone2->base + zone_frame_alloc(zone2, order);
721 
    else
 720 
    else
722 
        goto errout2;
 721 
        goto errout2;
723 
 
 722 
 
724 
    newzone = (zone_t *)PA2KA(PFN2ADDR(pfn));
 723 
    newzone = (zone_t *)PA2KA(PFN2ADDR(pfn));
725 
 
 724 
 
726 
    _zone_merge(newzone, zone1, zone2);
 725 
    _zone_merge(newzone, zone1, zone2);
727 
 
 726 
 
728 
    /* Free unneeded config frames */
 727 
    /* Free unneeded config frames */
729 
    zone_reduce_region(newzone, pfn - newzone->base,  cframes);
 728 
    zone_reduce_region(newzone, pfn - newzone->base,  cframes);
730 
    /* Subtract zone information from busy frames */
 729 
    /* Subtract zone information from busy frames */
731 
    newzone->busy_count -= cframes;
 730 
    newzone->busy_count -= cframes;
732 
 
 731 
 
733 
    /* Replace existing zones in zoneinfo list */
 732 
    /* Replace existing zones in zoneinfo list */
734 
    zones.info[z1] = newzone;
 733 
    zones.info[z1] = newzone;
735 
    for (i = z2 + 1; i < zones.count; i++)
 734 
    for (i = z2 + 1; i < zones.count; i++)
736 
        zones.info[i - 1] = zones.info[i];
 735 
        zones.info[i - 1] = zones.info[i];
737 
    zones.count--;
 736 
    zones.count--;
738 
 
 737 
 
739 
    /* Free old zone information */
 738 
    /* Free old zone information */
740 
    return_config_frames(newzone, zone1);
 739 
    return_config_frames(newzone, zone1);
741 
    return_config_frames(newzone, zone2);
 740 
    return_config_frames(newzone, zone2);
742 
errout2:
 741 
errout2:
743 
    /* Nobody is allowed to enter to zone, so we are safe
 742 
    /* Nobody is allowed to enter to zone, so we are safe
744 
     * to touch the spinlocks last time */
 743 
     * to touch the spinlocks last time */
745 
    spinlock_unlock(&zone1->lock);
 744 
    spinlock_unlock(&zone1->lock);
746 
    spinlock_unlock(&zone2->lock);
 745 
    spinlock_unlock(&zone2->lock);
747 
errout:
 746 
errout:
748 
    spinlock_unlock(&zones.lock);
 747 
    spinlock_unlock(&zones.lock);
749 
    interrupts_restore(ipl);
 748 
    interrupts_restore(ipl);
750 
}
 749 
}
751 
 
 750 
 
752 
/**
 751 
/**
753 
 * Merge all zones into one big zone
 752 
 * Merge all zones into one big zone
754 
 *
 753 
 *
755 
 * It is reasonable to do this on systems whose bios reports parts in chunks,
 754 
 * It is reasonable to do this on systems whose bios reports parts in chunks,
756 
 * so that we could have 1 zone (it's faster).
 755 
 * so that we could have 1 zone (it's faster).
757 
 */
 756 
 */
758 
void zone_merge_all(void)
 757 
void zone_merge_all(void)
759 
{
 758 
{
760 
    int count = zones.count;
 759 
    int count = zones.count;
761 
 
 760 
 
762 
    while (zones.count > 1 && --count) {
 761 
    while (zones.count > 1 && --count) {
763 
        zone_merge(0,1);
 762 
        zone_merge(0,1);
764 
        break;
 763 
        break;
765 
    }
 764 
    }
766 
}
 765 
}
767 
 
 766 
 
768 
/** Create frame zone
 767 
/** Create frame zone
769 
 *
 768 
 *
770 
 * Create new frame zone.
 769 
 * Create new frame zone.
771 
 *
 770 
 *
772 
 * @param start Physical address of the first frame within the zone.
 771 
 * @param start Physical address of the first frame within the zone.
773 
 * @param count Count of frames in zone
 772 
 * @param count Count of frames in zone
774 
 * @param z Address of configuration information of zone
 773 
 * @param z Address of configuration information of zone
775 
 * @param flags Zone flags.
 774 
 * @param flags Zone flags.
776 
 *
 775 
 *
777 
 * @return Initialized zone.
 776 
 * @return Initialized zone.
778 
 */
 777 
 */
779 
static void zone_construct(pfn_t start, count_t count, zone_t *z, int flags)
 778 
static void zone_construct(pfn_t start, count_t count, zone_t *z, int flags)
780 
{
 779 
{
781 
    int i;
 780 
    int i;
782 
    uint8_t max_order;
 781 
    uint8_t max_order;
783 
 
 782 
 
784 
    spinlock_initialize(&z->lock, "zone_lock");
 783 
    spinlock_initialize(&z->lock, "zone_lock");
785 
    z->base = start;
 784 
    z->base = start;
786 
    z->count = count;
 785 
    z->count = count;
787 
    z->flags = flags;
 786 
    z->flags = flags;
788 
    z->free_count = count;
 787 
    z->free_count = count;
789 
    z->busy_count = 0;
 788 
    z->busy_count = 0;
790 
 
 789 
 
791 
    /*
 790 
    /*
792 
     * Compute order for buddy system, initialize
 791 
     * Compute order for buddy system, initialize
793 
     */
 792 
     */
794 
    max_order = fnzb(count);
 793 
    max_order = fnzb(count);
795 
    z->buddy_system = (buddy_system_t *)&z[1];
 794 
    z->buddy_system = (buddy_system_t *)&z[1];
796 
   
 795 
   
797 
    buddy_system_create(z->buddy_system, max_order,
 796 
    buddy_system_create(z->buddy_system, max_order,
798 
                &zone_buddy_system_operations,
 797 
                &zone_buddy_system_operations,
799 
                (void *) z);
 798 
                (void *) z);
800 
   
 799 
   
801 
    /* Allocate frames _after_ the conframe */
 800 
    /* Allocate frames _after_ the conframe */
802 
    /* Check sizes */
 801 
    /* Check sizes */
803 
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
 802 
    z->frames = (frame_t *)((void *)z->buddy_system+buddy_conf_size(max_order));
804 
    for (i = 0; i<count; i++) {
 803 
    for (i = 0; i<count; i++) {
805 
        frame_initialize(&z->frames[i]);
 804 
        frame_initialize(&z->frames[i]);
806 
    }
 805 
    }
807 
   
 806 
   
808 
    /* Stuffing frames */
 807 
    /* Stuffing frames */
809 
    for (i = 0; i < count; i++) {
 808 
    for (i = 0; i < count; i++) {
810 
        z->frames[i].refcount = 0;
 809 
        z->frames[i].refcount = 0;
811 
        buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
 810 
        buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
812 
    }
 811 
    }
813 
}
 812 
}
814 
 
 813 
 
815 
/** Compute configuration data size for zone
 814 
/** Compute configuration data size for zone
816 
 *
 815 
 *
817 
 * @param count Size of zone in frames
 816 
 * @param count Size of zone in frames
818 
 * @return Size of zone configuration info (in bytes)
 817 
 * @return Size of zone configuration info (in bytes)
819 
 */
 818 
 */
820 
uintptr_t zone_conf_size(count_t count)
 819 
uintptr_t zone_conf_size(count_t count)
821 
{
 820 
{
822 
    int size = sizeof(zone_t) + count*sizeof(frame_t);
 821 
    int size = sizeof(zone_t) + count*sizeof(frame_t);
823 
    int max_order;
 822 
    int max_order;
824 
 
 823 
 
825 
    max_order = fnzb(count);
 824 
    max_order = fnzb(count);
826 
    size += buddy_conf_size(max_order);
 825 
    size += buddy_conf_size(max_order);
827 
    return size;
 826 
    return size;
828 
}
 827 
}
829 
 
 828 
 
830 
/** Create and add zone to system
 829 
/** Create and add zone to system
831 
 *
 830 
 *
832 
 * @param start First frame number (absolute)
 831 
 * @param start First frame number (absolute)
833 
 * @param count Size of zone in frames
 832 
 * @param count Size of zone in frames
834 
 * @param confframe Where configuration frames are supposed to be.
 833 
 * @param confframe Where configuration frames are supposed to be.
835 
 *                  Automatically checks, that we will not disturb the
 834 
 *                  Automatically checks, that we will not disturb the
836 
 *                  kernel and possibly init.
 835 
 *                  kernel and possibly init.
837 
 *                  If confframe is given _outside_ this zone, it is expected,
 836 
 *                  If confframe is given _outside_ this zone, it is expected,
838 
 *                  that the area is already marked BUSY and big enough
 837 
 *                  that the area is already marked BUSY and big enough
839 
 *                  to contain zone_conf_size() amount of data.
 838 
 *                  to contain zone_conf_size() amount of data.
840 
 *                  If the confframe is inside the area, the zone free frame
 839 
 *                  If the confframe is inside the area, the zone free frame
841 
 *                  information is modified not to include it.
 840 
 *                  information is modified not to include it.
842 
 *
 841 
 *
843 
 * @return Zone number or -1 on error
 842 
 * @return Zone number or -1 on error
844 
 */
 843 
 */
845 
int zone_create(pfn_t start, count_t count, pfn_t confframe, int flags)
 844 
int zone_create(pfn_t start, count_t count, pfn_t confframe, int flags)
846 
{
 845 
{
847 
    zone_t *z;
 846 
    zone_t *z;
848 
    uintptr_t addr;
 847 
    uintptr_t addr;
849 
    count_t confcount;
 848 
    count_t confcount;
850 
    int i;
 849 
    int i;
851 
    int znum;
 850 
    int znum;
852 
 
 851 
 
853 
    /* Theoretically we could have here 0, practically make sure
 852 
    /* Theoretically we could have here 0, practically make sure
854 
     * nobody tries to do that. If some platform requires, remove
 853 
     * nobody tries to do that. If some platform requires, remove
855 
     * the assert
 854 
     * the assert
856 
     */
 855 
     */
857 
    ASSERT(confframe);
 856 
    ASSERT(confframe);
858 
    /* If conframe is supposed to be inside our zone, then make sure
 857 
    /* If conframe is supposed to be inside our zone, then make sure
859 
     * it does not span kernel & init
 858 
     * it does not span kernel & init
860 
     */
 859 
     */
861 
    confcount = SIZE2FRAMES(zone_conf_size(count));
 860 
    confcount = SIZE2FRAMES(zone_conf_size(count));
862 
    if (confframe >= start && confframe < start+count) {
 861 
    if (confframe >= start && confframe < start+count) {
863 
        for (;confframe < start + count; confframe++) {
 862 
        for (;confframe < start + count; confframe++) {
864 
            addr = PFN2ADDR(confframe);
 863 
            addr = PFN2ADDR(confframe);
865 
            if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.base), config.kernel_size))
 864 
            if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.base), config.kernel_size))
866 
                continue;
 865 
                continue;
867 
           
 866 
           
868 
            if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.stack_base), config.stack_size))
 867 
            if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.stack_base), config.stack_size))
869 
                continue;
 868 
                continue;
870 
           
 869 
           
871 
            bool overlap = false;
 870 
            bool overlap = false;
872 
            count_t i;
 871 
            count_t i;
873 
            for (i = 0; i < init.cnt; i++)
 872 
            for (i = 0; i < init.cnt; i++)
874 
                if (overlaps(addr, PFN2ADDR(confcount), KA2PA(init.tasks[i].addr), init.tasks[i].size)) {
 873 
                if (overlaps(addr, PFN2ADDR(confcount), KA2PA(init.tasks[i].addr), init.tasks[i].size)) {
875 
                    overlap = true;
 874 
                    overlap = true;
876 
                    break;
 875 
                    break;
877 
                }
 876 
                }
878 
            if (overlap)
 877 
            if (overlap)
879 
                continue;
 878 
                continue;
880 
           
 879 
           
881 
            break;
 880 
            break;
882 
        }
 881 
        }
883 
        if (confframe >= start + count)
 882 
        if (confframe >= start + count)
884 
            panic("Cannot find configuration data for zone.");
 883 
            panic("Cannot find configuration data for zone.");
885 
    }
 884 
    }
886 
 
 885 
 
887 
    z = (zone_t *)PA2KA(PFN2ADDR(confframe));
 886 
    z = (zone_t *)PA2KA(PFN2ADDR(confframe));
888 
    zone_construct(start, count, z, flags);
 887 
    zone_construct(start, count, z, flags);
889 
    znum = zones_add_zone(z);
 888 
    znum = zones_add_zone(z);
890 
    if (znum == -1)
 889 
    if (znum == -1)
891 
        return -1;
 890 
        return -1;
892 
 
 891 
 
893 
    /* If confdata in zone, mark as unavailable */
 892 
    /* If confdata in zone, mark as unavailable */
894 
    if (confframe >= start && confframe < start+count)
 893 
    if (confframe >= start && confframe < start+count)
895 
        for (i=confframe; i<confframe+confcount; i++) {
 894 
        for (i=confframe; i<confframe+confcount; i++) {
896 
            zone_mark_unavailable(z, i - z->base);
 895 
            zone_mark_unavailable(z, i - z->base);
897 
        }
 896 
        }
898 
    return znum;
 897 
    return znum;
899 
}
 898 
}
900 
 
 899 
 
901 
/***************************************/
 900 
/***************************************/
902 
/* Frame functions */
 901 
/* Frame functions */
903 
 
 902 
 
904 
/** Set parent of frame */
 903 
/** Set parent of frame */
905 
void frame_set_parent(pfn_t pfn, void *data, int hint)
 904 
void frame_set_parent(pfn_t pfn, void *data, int hint)
906 
{
 905 
{
907 
    zone_t *zone = find_zone_and_lock(pfn, &hint);
 906 
    zone_t *zone = find_zone_and_lock(pfn, &hint);
908 
 
 907 
 
909 
    ASSERT(zone);
 908 
    ASSERT(zone);
910 
 
 909 
 
911 
    zone_get_frame(zone, pfn-zone->base)->parent = data;
 910 
    zone_get_frame(zone, pfn-zone->base)->parent = data;
912 
    spinlock_unlock(&zone->lock);
 911 
    spinlock_unlock(&zone->lock);
913 
}
 912 
}
914 
 
 913 
 
915 
void * frame_get_parent(pfn_t pfn, int hint)
 914 
void * frame_get_parent(pfn_t pfn, int hint)
916 
{
 915 
{
917 
    zone_t *zone = find_zone_and_lock(pfn, &hint);
 916 
    zone_t *zone = find_zone_and_lock(pfn, &hint);
918 
    void *res;
 917 
    void *res;
919 
 
 918 
 
920 
    ASSERT(zone);
 919 
    ASSERT(zone);
921 
    res = zone_get_frame(zone, pfn - zone->base)->parent;
 920 
    res = zone_get_frame(zone, pfn - zone->base)->parent;
922 
   
 921 
   
923 
    spinlock_unlock(&zone->lock);
 922 
    spinlock_unlock(&zone->lock);
924 
    return res;
 923 
    return res;
925 
}
 924 
}
926 
 
 925 
 
927 
/** Allocate power-of-two frames of physical memory.
 926 
/** Allocate power-of-two frames of physical memory.
928 
 *
 927 
 *
929 
 * @param order  Allocate exactly 2^order frames.
 928 
 * @param order  Allocate exactly 2^order frames.
930 
 * @param flags  Flags for host zone selection and address processing.
 929 
 * @param flags  Flags for host zone selection and address processing.
931 
 * @param pzone  Preferred zone
 930 
 * @param pzone  Preferred zone
932 
 *
 931 
 *
933 
 * @return Physical address of the allocated frame.
 932 
 * @return Physical address of the allocated frame.
934 
 *
 933 
 *
935 
 */
 934 
 */
936 
void * frame_alloc_generic(uint8_t order, int flags, int *pzone)
 935 
void * frame_alloc_generic(uint8_t order, int flags, int *pzone)
937 
{
 936 
{
938 
    ipl_t ipl;
 937 
    ipl_t ipl;
939 
    int freed;
 938 
    int freed;
940 
    pfn_t v;
 939 
    pfn_t v;
941 
    zone_t *zone;
 940 
    zone_t *zone;
942 
   
 941 
   
943 
loop:
 942 
loop:
944 
    ipl = interrupts_disable();
 943 
    ipl = interrupts_disable();
945 
   
 944 
   
946 
    /*
 945 
    /*
947 
     * First, find suitable frame zone.
 946 
     * First, find suitable frame zone.
948 
     */
 947 
     */
949 
    zone = find_free_zone_and_lock(order, pzone);
 948 
    zone = find_free_zone_and_lock(order, pzone);
950 
   
 949 
   
951 
    /* If no memory, reclaim some slab memory,
 950 
    /* If no memory, reclaim some slab memory,
952 
       if it does not help, reclaim all */
 951 
       if it does not help, reclaim all */
953 
    if (!zone && !(flags & FRAME_NO_RECLAIM)) {
 952 
    if (!zone && !(flags & FRAME_NO_RECLAIM)) {
954 
        freed = slab_reclaim(0);
 953 
        freed = slab_reclaim(0);
955 
        if (freed)
 954 
        if (freed)
956 
            zone = find_free_zone_and_lock(order, pzone);
 955 
            zone = find_free_zone_and_lock(order, pzone);
957 
        if (!zone) {
 956 
        if (!zone) {
958 
            freed = slab_reclaim(SLAB_RECLAIM_ALL);
 957 
            freed = slab_reclaim(SLAB_RECLAIM_ALL);
959 
            if (freed)
 958 
            if (freed)
960 
                zone = find_free_zone_and_lock(order, pzone);
 959 
                zone = find_free_zone_and_lock(order, pzone);
961 
        }
 960 
        }
962 
    }
 961 
    }
963 
    if (!zone) {
 962 
    if (!zone) {
964 
        /*
 963 
        /*
965 
         * TODO: Sleep until frames are available again.
 964 
         * TODO: Sleep until frames are available again.
966 
         */
 965 
         */
967 
        interrupts_restore(ipl);
 966 
        interrupts_restore(ipl);
968 
 
 967 
 
969 
        if (flags & FRAME_ATOMIC)
 968 
        if (flags & FRAME_ATOMIC)
970 
            return 0;
 969 
            return 0;
971 
       
 970 
       
972 
        panic("Sleep not implemented.\n");
 971 
        panic("Sleep not implemented.\n");
973 
        goto loop;
 972 
        goto loop;
974 
    }
 973 
    }
975 
   
 974 
   
976 
    v = zone_frame_alloc(zone, order);
 975 
    v = zone_frame_alloc(zone, order);
977 
    v += zone->base;
 976 
    v += zone->base;
978 
 
 977 
 
979 
    spinlock_unlock(&zone->lock);
 978 
    spinlock_unlock(&zone->lock);
980 
    interrupts_restore(ipl);
 979 
    interrupts_restore(ipl);
981 
 
 980 
 
982 
    if (flags & FRAME_KA)
 981 
    if (flags & FRAME_KA)
983 
        return (void *)PA2KA(PFN2ADDR(v));
 982 
        return (void *)PA2KA(PFN2ADDR(v));
984 
    return (void *)PFN2ADDR(v);
 983 
    return (void *)PFN2ADDR(v);
985 
}
 984 
}
986 
 
 985 
 
987 
/** Free a frame.
 986 
/** Free a frame.
988 
 *
 987 
 *
989 
 * Find respective frame structure for supplied physical frame address.
 988 
 * Find respective frame structure for supplied physical frame address.
990 
 * Decrement frame reference count.
 989 
 * Decrement frame reference count.
991 
 * If it drops to zero, move the frame structure to free list.
 990 
 * If it drops to zero, move the frame structure to free list.
992 
 *
 991 
 *
993 
 * @param Frame Physical Address of of the frame to be freed.
 992 
 * @param Frame Physical Address of of the frame to be freed.
994 
 */
 993 
 */
995 
void frame_free(uintptr_t frame)
 994 
void frame_free(uintptr_t frame)
996 
{
 995 
{
997 
    ipl_t ipl;
 996 
    ipl_t ipl;
998 
    zone_t *zone;
 997 
    zone_t *zone;
999 
    pfn_t pfn = ADDR2PFN(frame);
 998 
    pfn_t pfn = ADDR2PFN(frame);
1000 
 
 999 
 
1001 
    ipl = interrupts_disable();
 1000 
    ipl = interrupts_disable();
1002 
   
 1001 
   
1003 
    /*
 1002 
    /*
1004 
     * First, find host frame zone for addr.
 1003 
     * First, find host frame zone for addr.
1005 
     */
 1004 
     */
1006 
    zone = find_zone_and_lock(pfn,NULL);
 1005 
    zone = find_zone_and_lock(pfn,NULL);
1007 
    ASSERT(zone);
 1006 
    ASSERT(zone);
1008 
   
 1007 
   
1009 
    zone_frame_free(zone, pfn-zone->base);
 1008 
    zone_frame_free(zone, pfn-zone->base);
1010 
   
 1009 
   
1011 
    spinlock_unlock(&zone->lock);
 1010 
    spinlock_unlock(&zone->lock);
1012 
    interrupts_restore(ipl);
 1011 
    interrupts_restore(ipl);
1013 
}
 1012 
}
1014 
 
 1013 
 
1015 
/** Add reference to frame.
 1014 
/** Add reference to frame.
1016 
 *
 1015 
 *
1017 
 * Find respective frame structure for supplied PFN and
 1016 
 * Find respective frame structure for supplied PFN and
1018 
 * increment frame reference count.
 1017 
 * increment frame reference count.
1019 
 *
 1018 
 *
1020 
 * @param pfn Frame number of the frame to be freed.
 1019 
 * @param pfn Frame number of the frame to be freed.
1021 
 */
 1020 
 */
1022 
void frame_reference_add(pfn_t pfn)
 1021 
void frame_reference_add(pfn_t pfn)
1023 
{
 1022 
{
1024 
    ipl_t ipl;
 1023 
    ipl_t ipl;
1025 
    zone_t *zone;
 1024 
    zone_t *zone;
1026 
    frame_t *frame;
 1025 
    frame_t *frame;
1027 
 
 1026 
 
1028 
    ipl = interrupts_disable();
 1027 
    ipl = interrupts_disable();
1029 
   
 1028 
   
1030 
    /*
 1029 
    /*
1031 
     * First, find host frame zone for addr.
 1030 
     * First, find host frame zone for addr.
1032 
     */
 1031 
     */
1033 
    zone = find_zone_and_lock(pfn,NULL);
 1032 
    zone = find_zone_and_lock(pfn,NULL);
1034 
    ASSERT(zone);
 1033 
    ASSERT(zone);
1035 
   
 1034 
   
1036 
    frame = &zone->frames[pfn-zone->base];
 1035 
    frame = &zone->frames[pfn-zone->base];
1037 
    frame->refcount++;
 1036 
    frame->refcount++;
1038 
   
 1037 
   
1039 
    spinlock_unlock(&zone->lock);
 1038 
    spinlock_unlock(&zone->lock);
1040 
    interrupts_restore(ipl);
 1039 
    interrupts_restore(ipl);
1041 
}
 1040 
}
1042 
 
 1041 
 
1043 
/** Mark given range unavailable in frame zones */
 1042 
/** Mark given range unavailable in frame zones */
1044 
void frame_mark_unavailable(pfn_t start, count_t count)
 1043 
void frame_mark_unavailable(pfn_t start, count_t count)
1045 
{
 1044 
{
1046 
    int i;
 1045 
    int i;
1047 
    zone_t *zone;
 1046 
    zone_t *zone;
1048 
    int prefzone = 0;
 1047 
    int prefzone = 0;
1049 
   
 1048 
   
1050 
    for (i=0; i < count; i++) {
 1049 
    for (i=0; i < count; i++) {
1051 
        zone = find_zone_and_lock(start + i, &prefzone);
 1050 
        zone = find_zone_and_lock(start + i, &prefzone);
1052 
        if (!zone) /* PFN not found */
 1051 
        if (!zone) /* PFN not found */
1053 
            continue;
 1052 
            continue;
1054 
        zone_mark_unavailable(zone, start + i - zone->base);
 1053 
        zone_mark_unavailable(zone, start + i - zone->base);
1055 
 
 1054 
 
1056 
        spinlock_unlock(&zone->lock);
 1055 
        spinlock_unlock(&zone->lock);
1057 
    }
 1056 
    }
1058 
}
 1057 
}
1059 
 
 1058 
 
1060 
/** Initialize physical memory management
 1059 
/** Initialize physical memory management
1061 
 *
 1060 
 *
1062 
 * Initialize physical memory managemnt.
 1061 
 * Initialize physical memory managemnt.
1063 
 */
 1062 
 */
1064 
void frame_init(void)
 1063 
void frame_init(void)
1065 
{
 1064 
{
1066 
    if (config.cpu_active == 1) {
 1065 
    if (config.cpu_active == 1) {
1067 
        zones.count = 0;
 1066 
        zones.count = 0;
1068 
        spinlock_initialize(&zones.lock, "zones.lock");
 1067 
        spinlock_initialize(&zones.lock, "zones.lock");
1069 
    }
 1068 
    }
1070 
    /* Tell the architecture to create some memory */
 1069 
    /* Tell the architecture to create some memory */
1071 
    frame_arch_init();
 1070 
    frame_arch_init();
1072 
    if (config.cpu_active == 1) {
 1071 
    if (config.cpu_active == 1) {
1073 
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)), SIZE2FRAMES(config.kernel_size));
 1072 
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)), SIZE2FRAMES(config.kernel_size));
1074 
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)), SIZE2FRAMES(config.stack_size));
 1073 
        frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)), SIZE2FRAMES(config.stack_size));
1075 
       
 1074 
       
1076 
        count_t i;
 1075 
        count_t i;
1077 
        for (i = 0; i < init.cnt; i++)
 1076 
        for (i = 0; i < init.cnt; i++)
1078 
            frame_mark_unavailable(ADDR2PFN(KA2PA(init.tasks[i].addr)), SIZE2FRAMES(init.tasks[i].size));
 1077 
            frame_mark_unavailable(ADDR2PFN(KA2PA(init.tasks[i].addr)), SIZE2FRAMES(init.tasks[i].size));
1079 
 
 1078 
 
1080 
        if (ballocs.size)
 1079 
        if (ballocs.size)
1081 
            frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)), SIZE2FRAMES(ballocs.size));
 1080 
            frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)), SIZE2FRAMES(ballocs.size));
1082 
 
 1081 
 
1083 
        /* Black list first frame, as allocating NULL would
 1082 
        /* Black list first frame, as allocating NULL would
1084 
         * fail in some places */
 1083 
         * fail in some places */
1085 
        frame_mark_unavailable(0, 1);
 1084 
        frame_mark_unavailable(0, 1);
1086 
    }
 1085 
    }
1087 
}
 1086 
}
1088 
 
 1087 
 
1089 
 
 1088 
 
1090 
 
 1089 
 
1091 
/** Prints list of zones
 1090 
/** Prints list of zones
1092 
 *
 1091 
 *
1093 
 */
 1092 
 */
1094 
void zone_print_list(void) {
 1093 
void zone_print_list(void) {
1095 
    zone_t *zone = NULL;
 1094 
    zone_t *zone = NULL;
1096 
    int i;
 1095 
    int i;
1097 
    ipl_t ipl;
 1096 
    ipl_t ipl;
1098 
 
 1097 
 
1099 
    ipl = interrupts_disable();
 1098 
    ipl = interrupts_disable();
1100 
    spinlock_lock(&zones.lock);
 1099 
    spinlock_lock(&zones.lock);
1101 
    printf("#  base address free frames  busy frames\n");
 1100 
    printf("#  base address free frames  busy frames\n");
1102 
    printf("-- ------------ ------------ ------------\n");
 1101 
    printf("-- ------------ ------------ ------------\n");
1103 
    for (i = 0; i < zones.count; i++) {
 1102 
    for (i = 0; i < zones.count; i++) {
1104 
        zone = zones.info[i];
 1103 
        zone = zones.info[i];
1105 
        spinlock_lock(&zone->lock);
 1104 
        spinlock_lock(&zone->lock);
1106 
        printf("%-2d %12p %12zd %12zd\n", i, PFN2ADDR(zone->base), zone->free_count, zone->busy_count);
 1105 
        printf("%-2d %12p %12zd %12zd\n", i, PFN2ADDR(zone->base), zone->free_count, zone->busy_count);
1107 
        spinlock_unlock(&zone->lock);
 1106 
        spinlock_unlock(&zone->lock);
1108 
    }
 1107 
    }
1109 
    spinlock_unlock(&zones.lock);
 1108 
    spinlock_unlock(&zones.lock);
1110 
    interrupts_restore(ipl);
 1109 
    interrupts_restore(ipl);
1111 
}
 1110 
}
1112 
 
 1111 
 
1113 
/** Prints zone details.
 1112 
/** Prints zone details.
1114 
 *
 1113 
 *
1115 
 * @param num Zone base address or zone number.
 1114 
 * @param num Zone base address or zone number.
1116 
 */
 1115 
 */
1117 
void zone_print_one(int num) {
 1116 
void zone_print_one(int num) {
1118 
    zone_t *zone = NULL;
 1117 
    zone_t *zone = NULL;
1119 
    ipl_t ipl;
 1118 
    ipl_t ipl;
1120 
    int i;
 1119 
    int i;
1121 
 
 1120 
 
1122 
    ipl = interrupts_disable();
 1121 
    ipl = interrupts_disable();
1123 
    spinlock_lock(&zones.lock);
 1122 
    spinlock_lock(&zones.lock);
1124 
 
 1123 
 
1125 
    for (i = 0; i < zones.count; i++) {
 1124 
    for (i = 0; i < zones.count; i++) {
1126 
        if (i == num || PFN2ADDR(zones.info[i]->base) == num) {
 1125 
        if (i == num || PFN2ADDR(zones.info[i]->base) == num) {
1127 
            zone = zones.info[i];
 1126 
            zone = zones.info[i];
1128 
            break;
 1127 
            break;
1129 
        }
 1128 
        }
1130 
    }
 1129 
    }
1131 
    if (!zone) {
 1130 
    if (!zone) {
1132 
        printf("Zone not found.\n");
 1131 
        printf("Zone not found.\n");
1133 
        goto out;
 1132 
        goto out;
1134 
    }
 1133 
    }
1135 
   
 1134 
   
1136 
    spinlock_lock(&zone->lock);
 1135 
    spinlock_lock(&zone->lock);
1137 
    printf("Memory zone information\n");
 1136 
    printf("Memory zone information\n");
1138 
    printf("Zone base address: %#.*p\n", sizeof(uintptr_t) * 2, PFN2ADDR(zone->base));
 1137 
    printf("Zone base address: %#.*p\n", sizeof(uintptr_t) * 2, PFN2ADDR(zone->base));
1139 
    printf("Zone size: %zd frames (%zdK)\n", zone->count, ((zone->count) * FRAME_SIZE) >> 10);
 1138 
    printf("Zone size: %zd frames (%zdK)\n", zone->count, ((zone->count) * FRAME_SIZE) >> 10);
1140 
    printf("Allocated space: %zd frames (%zdK)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
 1139 
    printf("Allocated space: %zd frames (%zdK)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
1141 
    printf("Available space: %zd frames (%zdK)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
 1140 
    printf("Available space: %zd frames (%zdK)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
1142 
    buddy_system_structure_print(zone->buddy_system, FRAME_SIZE);
 1141 
    buddy_system_structure_print(zone->buddy_system, FRAME_SIZE);
1143 
   
 1142 
   
1144 
    spinlock_unlock(&zone->lock);
 1143 
    spinlock_unlock(&zone->lock);
1145 
out:
 1144 
out:
1146 
    spinlock_unlock(&zones.lock);
 1145 
    spinlock_unlock(&zones.lock);
1147 
    interrupts_restore(ipl);
 1146 
    interrupts_restore(ipl);
1148 
}
 1147 
}
1149 
 
 1148 
 
1150 
/** @}
 1149 
/** @}
1151 
 */
 1150 
 */
1152 
 
 1151