Subversion Repositories HelenOS

Rev

Rev 3425 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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