source: branches/minix3-book/servers/pm/alloc.c@ 4

Last change on this file since 4 was 4, checked in by Mattia Monga, 13 years ago

Importazione sorgenti libro
File size: 8.0 KB
Line 
1/* This file is concerned with allocating and freeing arbitrary-size blocks of
2 * physical memory on behalf of the FORK and EXEC system calls. The key data
3 * structure used is the hole table, which maintains a list of holes in memory.
4 * It is kept sorted in order of increasing memory address. The addresses
5 * it contains refers to physical memory, starting at absolute address 0
6 * (i.e., they are not relative to the start of PM). During system
7 * initialization, that part of memory containing the interrupt vectors,
8 * kernel, and PM are "allocated" to mark them as not available and to
9 * remove them from the hole list.
10 *
11 * The entry points into this file are:
12 * alloc_mem: allocate a given sized chunk of memory
13 * free_mem: release a previously allocated chunk of memory
14 * mem_init: initialize the tables when PM start up
15 * max_hole: returns the largest hole currently available
16 */
17
18#include "pm.h"
19#include <minix/com.h>
20#include <minix/callnr.h>
21#include <signal.h>
22#include <stdlib.h>
23#include "mproc.h"
24#include "../../kernel/const.h"
25#include "../../kernel/config.h"
26#include "../../kernel/type.h"
27
28#define NR_HOLES (2*NR_PROCS) /* max # entries in hole table */
29#define NIL_HOLE (struct hole *) 0
30
31PRIVATE struct hole {
32 struct hole *h_next; /* pointer to next entry on the list */
33 phys_clicks h_base; /* where does the hole begin? */
34 phys_clicks h_len; /* how big is the hole? */
35} hole[NR_HOLES];
36
37PRIVATE struct hole *hole_head; /* pointer to first hole */
38PRIVATE struct hole *free_slots;/* ptr to list of unused table slots */
39#define swap_base ((phys_clicks) -1)
40
41FORWARD _PROTOTYPE( void del_slot, (struct hole *prev_ptr, struct hole *hp) );
42FORWARD _PROTOTYPE( void merge, (struct hole *hp) );
43#define swap_out() (0)
44
45/*===========================================================================*
46 * alloc_mem *
47 *===========================================================================*/
48PUBLIC phys_clicks alloc_mem(clicks)
49phys_clicks clicks; /* amount of memory requested */
50{
51/* Allocate a block of memory from the free list using first fit. The block
52 * consists of a sequence of contiguous bytes, whose length in clicks is
53 * given by 'clicks'. A pointer to the block is returned. The block is
54 * always on a click boundary. This procedure is called when memory is
55 * needed for FORK or EXEC. Swap other processes out if needed.
56 */
57 register struct hole *hp, *prev_ptr;
58 phys_clicks old_base;
59
60 do {
61 prev_ptr = NIL_HOLE;
62 hp = hole_head;
63 while (hp != NIL_HOLE && hp->h_base < swap_base) {
64 if (hp->h_len >= clicks) {
65 /* We found a hole that is big enough. Use it. */
66 old_base = hp->h_base; /* remember where it started */
67 hp->h_base += clicks; /* bite a piece off */
68 hp->h_len -= clicks; /* ditto */
69
70 /* Delete the hole if used up completely. */
71 if (hp->h_len == 0) del_slot(prev_ptr, hp);
72
73 /* Return the start address of the acquired block. */
74 return(old_base);
75 }
76
77 prev_ptr = hp;
78 hp = hp->h_next;
79 }
80 } while (swap_out()); /* try to swap some other process out */
81 return(NO_MEM);
82}
83
84/*===========================================================================*
85 * free_mem *
86 *===========================================================================*/
87PUBLIC void free_mem(base, clicks)
88phys_clicks base; /* base address of block to free */
89phys_clicks clicks; /* number of clicks to free */
90{
91/* Return a block of free memory to the hole list. The parameters tell where
92 * the block starts in physical memory and how big it is. The block is added
93 * to the hole list. If it is contiguous with an existing hole on either end,
94 * it is merged with the hole or holes.
95 */
96 register struct hole *hp, *new_ptr, *prev_ptr;
97
98 if (clicks == 0) return;
99 if ( (new_ptr = free_slots) == NIL_HOLE)
100 panic(__FILE__,"hole table full", NO_NUM);
101 new_ptr->h_base = base;
102 new_ptr->h_len = clicks;
103 free_slots = new_ptr->h_next;
104 hp = hole_head;
105
106 /* If this block's address is numerically less than the lowest hole currently
107 * available, or if no holes are currently available, put this hole on the
108 * front of the hole list.
109 */
110 if (hp == NIL_HOLE || base <= hp->h_base) {
111 /* Block to be freed goes on front of the hole list. */
112 new_ptr->h_next = hp;
113 hole_head = new_ptr;
114 merge(new_ptr);
115 return;
116 }
117
118 /* Block to be returned does not go on front of hole list. */
119 prev_ptr = NIL_HOLE;
120 while (hp != NIL_HOLE && base > hp->h_base) {
121 prev_ptr = hp;
122 hp = hp->h_next;
123 }
124
125 /* We found where it goes. Insert block after 'prev_ptr'. */
126 new_ptr->h_next = prev_ptr->h_next;
127 prev_ptr->h_next = new_ptr;
128 merge(prev_ptr); /* sequence is 'prev_ptr', 'new_ptr', 'hp' */
129}
130
131/*===========================================================================*
132 * del_slot *
133 *===========================================================================*/
134PRIVATE void del_slot(prev_ptr, hp)
135/* pointer to hole entry just ahead of 'hp' */
136register struct hole *prev_ptr;
137/* pointer to hole entry to be removed */
138register struct hole *hp;
139{
140/* Remove an entry from the hole list. This procedure is called when a
141 * request to allocate memory removes a hole in its entirety, thus reducing
142 * the numbers of holes in memory, and requiring the elimination of one
143 * entry in the hole list.
144 */
145 if (hp == hole_head)
146 hole_head = hp->h_next;
147 else
148 prev_ptr->h_next = hp->h_next;
149
150 hp->h_next = free_slots;
151 free_slots = hp;
152}
153
154/*===========================================================================*
155 * merge *
156 *===========================================================================*/
157PRIVATE void merge(hp)
158register struct hole *hp; /* ptr to hole to merge with its successors */
159{
160/* Check for contiguous holes and merge any found. Contiguous holes can occur
161 * when a block of memory is freed, and it happens to abut another hole on
162 * either or both ends. The pointer 'hp' points to the first of a series of
163 * three holes that can potentially all be merged together.
164 */
165 register struct hole *next_ptr;
166
167 /* If 'hp' points to the last hole, no merging is possible. If it does not,
168 * try to absorb its successor into it and free the successor's table entry.
169 */
170 if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
171 if (hp->h_base + hp->h_len == next_ptr->h_base) {
172 hp->h_len += next_ptr->h_len; /* first one gets second one's mem */
173 del_slot(hp, next_ptr);
174 } else {
175 hp = next_ptr;
176 }
177
178 /* If 'hp' now points to the last hole, return; otherwise, try to absorb its
179 * successor into it.
180 */
181 if ( (next_ptr = hp->h_next) == NIL_HOLE) return;
182 if (hp->h_base + hp->h_len == next_ptr->h_base) {
183 hp->h_len += next_ptr->h_len;
184 del_slot(hp, next_ptr);
185 }
186}
187
188/*===========================================================================*
189 * mem_init *
190 *===========================================================================*/
191PUBLIC void mem_init(chunks, free)
192struct memory *chunks; /* list of free memory chunks */
193phys_clicks *free; /* memory size summaries */
194{
195/* Initialize hole lists. There are two lists: 'hole_head' points to a linked
196 * list of all the holes (unused memory) in the system; 'free_slots' points to
197 * a linked list of table entries that are not in use. Initially, the former
198 * list has one entry for each chunk of physical memory, and the second
199 * list links together the remaining table slots. As memory becomes more
200 * fragmented in the course of time (i.e., the initial big holes break up into
201 * smaller holes), new table slots are needed to represent them. These slots
202 * are taken from the list headed by 'free_slots'.
203 */
204 int i;
205 register struct hole *hp;
206
207 /* Put all holes on the free list. */
208 for (hp = &hole[0]; hp < &hole[NR_HOLES]; hp++) hp->h_next = hp + 1;
209 hole[NR_HOLES-1].h_next = NIL_HOLE;
210 hole_head = NIL_HOLE;
211 free_slots = &hole[0];
212
213 /* Use the chunks of physical memory to allocate holes. */
214 *free = 0;
215 for (i=NR_MEMS-1; i>=0; i--) {
216 if (chunks[i].size > 0) {
217 free_mem(chunks[i].base, chunks[i].size);
218 *free += chunks[i].size;
219 }
220 }
221}
Note: See TracBrowser for help on using the repository browser.