Annotation of src/usr.bin/ssh/monitor_mm.c, Revision 1.4
1.1 provos 1: /*
2: * Copyright 2002 Niels Provos <provos@citi.umich.edu>
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: *
14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: */
25:
26: #include "includes.h"
1.4 ! stevesk 27: RCSID("$OpenBSD: monitor_mm.c,v 1.3 2002/03/19 10:41:32 markus Exp $");
1.1 provos 28:
29: #include <sys/mman.h>
30:
31: #include "ssh.h"
32: #include "xmalloc.h"
33: #include "log.h"
34: #include "monitor_mm.h"
35:
36: static int
37: mm_compare(struct mm_share *a, struct mm_share *b)
38: {
39: return ((char *)a->address - (char *)b->address);
40: }
41:
42: RB_GENERATE(mmtree, mm_share, next, mm_compare)
43:
44: static struct mm_share *
45: mm_make_entry(struct mm_master *mm, struct mmtree *head,
46: void *address, size_t size)
47: {
48: struct mm_share *tmp, *tmp2;
49:
50: if (mm->mmalloc == NULL)
51: tmp = xmalloc(sizeof(struct mm_share));
52: else
53: tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share));
54: tmp->address = address;
55: tmp->size = size;
56:
57: tmp2 = RB_INSERT(mmtree, head, tmp);
58: if (tmp2 != NULL)
1.4 ! stevesk 59: fatal("mm_make_entry(%p): double address %p->%p(%lu)",
! 60: mm, tmp2, address, (u_long)size);
1.1 provos 61:
62: return (tmp);
63: }
64:
65: /* Creates a shared memory area of a certain size */
66:
67: struct mm_master *
68: mm_create(struct mm_master *mmalloc, size_t size)
69: {
70: void *address;
71: struct mm_master *mm;
72:
73: if (mmalloc == NULL)
74: mm = xmalloc(sizeof(struct mm_master));
75: else
76: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
77:
1.3 markus 78: /*
1.1 provos 79: * If the memory map has a mm_master it can be completely
80: * shared including authentication between the child
81: * and the client.
82: */
83: mm->mmalloc = mmalloc;
84:
85: address = mmap(NULL, size, PROT_WRITE|PROT_READ, MAP_ANON|MAP_SHARED,
86: -1, 0);
87: if (address == MAP_FAILED)
1.4 ! stevesk 88: fatal("mmap(%lu)", (u_long)size);
1.1 provos 89:
90: mm->address = address;
91: mm->size = size;
92:
93: RB_INIT(&mm->rb_free);
94: RB_INIT(&mm->rb_allocated);
95:
96: mm_make_entry(mm, &mm->rb_free, address, size);
97:
98: return (mm);
99: }
100:
101: /* Frees either the allocated or the free list */
102:
1.2 markus 103: static void
1.1 provos 104: mm_freelist(struct mm_master *mmalloc, struct mmtree *head)
105: {
106: struct mm_share *mms, *next;
107:
108: for (mms = RB_ROOT(head); mms; mms = next) {
109: next = RB_NEXT(mmtree, head, mms);
110: RB_REMOVE(mmtree, head, mms);
111: if (mmalloc == NULL)
112: xfree(mms);
113: else
114: mm_free(mmalloc, mms);
115: }
116: }
117:
118: /* Destroys a memory mapped area */
119:
120: void
121: mm_destroy(struct mm_master *mm)
122: {
123: mm_freelist(mm->mmalloc, &mm->rb_free);
124: mm_freelist(mm->mmalloc, &mm->rb_allocated);
125:
126: if (munmap(mm->address, mm->size) == -1)
1.4 ! stevesk 127: fatal("munmap(%p, %lu)", mm->address, (u_long)mm->size);
1.1 provos 128: if (mm->mmalloc == NULL)
129: xfree(mm);
130: else
131: mm_free(mm->mmalloc, mm);
132: }
133:
134: void *
135: mm_xmalloc(struct mm_master *mm, size_t size)
136: {
137: void *address;
138:
139: address = mm_malloc(mm, size);
140: if (address == NULL)
1.4 ! stevesk 141: fatal("%s: mm_malloc(%lu)", __FUNCTION__, (u_long)size);
1.1 provos 142: return (address);
143: }
144:
145:
146: /* Allocates data from a memory mapped area */
147:
148: void *
149: mm_malloc(struct mm_master *mm, size_t size)
150: {
151: struct mm_share *mms, *tmp;
152:
153: if (size == 0)
154: fatal("mm_malloc: try to allocate 0 space");
155:
156: size = ((size + MM_MINSIZE - 1) / MM_MINSIZE) * MM_MINSIZE;
157:
158: RB_FOREACH(mms, mmtree, &mm->rb_free) {
159: if (mms->size >= size)
160: break;
161: }
162:
163: if (mms == NULL)
164: return (NULL);
165:
1.3 markus 166: /* Debug */
1.1 provos 167: memset(mms->address, 0xd0, size);
168:
169: tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size);
170:
171: /* Does not change order in RB tree */
172: mms->size -= size;
173: mms->address = (u_char *)mms->address + size;
174:
175: if (mms->size == 0) {
176: RB_REMOVE(mmtree, &mm->rb_free, mms);
177: if (mm->mmalloc == NULL)
178: xfree(mms);
179: else
180: mm_free(mm->mmalloc, mms);
181: }
182:
183: return (tmp->address);
184: }
185:
186: /* Frees memory in a memory mapped area */
187:
188: void
189: mm_free(struct mm_master *mm, void *address)
190: {
191: struct mm_share *mms, *prev, tmp;
192:
193: tmp.address = address;
194: mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp);
195: if (mms == NULL)
196: fatal("mm_free(%p): can not find %p", mm, address);
197:
1.3 markus 198: /* Debug */
1.1 provos 199: memset(mms->address, 0xd0, mms->size);
200:
201: /* Remove from allocated list and insert in free list */
202: RB_REMOVE(mmtree, &mm->rb_allocated, mms);
203: if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL)
204: fatal("mm_free(%p): double address %p", mm, address);
205:
206: /* Find previous entry */
207: prev = mms;
208: if (RB_LEFT(prev, next)) {
209: prev = RB_LEFT(prev, next);
210: while (RB_RIGHT(prev, next))
211: prev = RB_RIGHT(prev, next);
212: } else {
213: if (RB_PARENT(prev, next) &&
214: (prev == RB_RIGHT(RB_PARENT(prev, next), next)))
215: prev = RB_PARENT(prev, next);
216: else {
217: while (RB_PARENT(prev, next) &&
218: (prev == RB_LEFT(RB_PARENT(prev, next), next)))
219: prev = RB_PARENT(prev, next);
220: prev = RB_PARENT(prev, next);
221: }
222: }
223:
224: /* Check if range does not overlap */
225: if (prev != NULL && MM_ADDRESS_END(prev) > address)
1.4 ! stevesk 226: fatal("mm_free: memory corruption: %p(%lu) > %p",
! 227: prev->address, (u_long)prev->size, address);
1.1 provos 228:
229: /* See if we can merge backwards */
230: if (prev != NULL && MM_ADDRESS_END(prev) == address) {
231: prev->size += mms->size;
232: RB_REMOVE(mmtree, &mm->rb_free, mms);
233: if (mm->mmalloc == NULL)
234: xfree(mms);
235: else
236: mm_free(mm->mmalloc, mms);
237: } else
238: prev = mms;
239:
240: if (prev == NULL)
241: return;
242:
243: /* Check if we can merge forwards */
244: mms = RB_NEXT(mmtree, &mm->rb_free, prev);
245: if (mms == NULL)
246: return;
247:
248: if (MM_ADDRESS_END(prev) > mms->address)
1.4 ! stevesk 249: fatal("mm_free: memory corruption: %p < %p(%lu)",
! 250: mms->address, prev->address, (u_long)prev->size);
1.1 provos 251: if (MM_ADDRESS_END(prev) != mms->address)
252: return;
253:
254: prev->size += mms->size;
255: RB_REMOVE(mmtree, &mm->rb_free, mms);
256:
257: if (mm->mmalloc == NULL)
258: xfree(mms);
259: else
260: mm_free(mm->mmalloc, mms);
261: }
262:
1.2 markus 263: static void
1.1 provos 264: mm_sync_list(struct mmtree *oldtree, struct mmtree *newtree,
265: struct mm_master *mm, struct mm_master *mmold)
266: {
267: struct mm_master *mmalloc = mm->mmalloc;
268: struct mm_share *mms, *new;
269:
270: /* Sync free list */
271: RB_FOREACH(mms, mmtree, oldtree) {
272: /* Check the values */
273: mm_memvalid(mmold, mms, sizeof(struct mm_share));
274: mm_memvalid(mm, mms->address, mms->size);
275:
276: new = mm_xmalloc(mmalloc, sizeof(struct mm_share));
277: memcpy(new, mms, sizeof(struct mm_share));
278: RB_INSERT(mmtree, newtree, new);
279: }
280: }
281:
282: void
283: mm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc)
284: {
285: struct mm_master *mm;
286: struct mm_master *mmalloc;
287: struct mm_master *mmold;
288: struct mmtree rb_free, rb_allocated;
289:
290: debug3("%s: Share sync", __FUNCTION__);
291:
292: mm = *pmm;
293: mmold = mm->mmalloc;
294: mm_memvalid(mmold, mm, sizeof(*mm));
295:
296: mmalloc = mm_create(NULL, mm->size);
297: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
298: memcpy(mm, *pmm, sizeof(struct mm_master));
299: mm->mmalloc = mmalloc;
300:
301: rb_free = mm->rb_free;
302: rb_allocated = mm->rb_allocated;
303:
304: RB_INIT(&mm->rb_free);
305: RB_INIT(&mm->rb_allocated);
306:
307: mm_sync_list(&rb_free, &mm->rb_free, mm, mmold);
308: mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold);
309:
310: mm_destroy(mmold);
311:
312: *pmm = mm;
313: *pmmalloc = mmalloc;
314:
315: debug3("%s: Share sync end", __FUNCTION__);
316: }
317:
318: void
319: mm_memvalid(struct mm_master *mm, void *address, size_t size)
320: {
321: void *end = (u_char *)address + size;
322:
323: if (address < mm->address)
324: fatal("mm_memvalid: address too small: %p", address);
325: if (end < address)
326: fatal("mm_memvalid: end < address: %p < %p", end, address);
327: if (end > (void *)((u_char *)mm->address + mm->size))
328: fatal("mm_memvalid: address too large: %p", address);
329: }