Subversion Repositories HelenOS

Rev

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

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