Subversion Repositories HelenOS

Rev

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

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