Annotation of src/usr.bin/ssh/monitor_mm.c, Revision 1.7
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.7 ! millert 27: RCSID("$OpenBSD: monitor_mm.c,v 1.6 2002/06/04 23:05:49 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: {
1.7 ! millert 39: long diff = (char *)a->address - (char *)b->address;
! 40:
! 41: if (diff == 0)
! 42: return (0);
! 43: else if (diff < 0)
! 44: return (-1);
! 45: else
! 46: return (1);
1.1 provos 47: }
48:
49: RB_GENERATE(mmtree, mm_share, next, mm_compare)
50:
51: static struct mm_share *
52: mm_make_entry(struct mm_master *mm, struct mmtree *head,
53: void *address, size_t size)
54: {
55: struct mm_share *tmp, *tmp2;
56:
57: if (mm->mmalloc == NULL)
58: tmp = xmalloc(sizeof(struct mm_share));
59: else
60: tmp = mm_xmalloc(mm->mmalloc, sizeof(struct mm_share));
61: tmp->address = address;
62: tmp->size = size;
63:
64: tmp2 = RB_INSERT(mmtree, head, tmp);
65: if (tmp2 != NULL)
1.4 stevesk 66: fatal("mm_make_entry(%p): double address %p->%p(%lu)",
67: mm, tmp2, address, (u_long)size);
1.1 provos 68:
69: return (tmp);
70: }
71:
72: /* Creates a shared memory area of a certain size */
73:
74: struct mm_master *
75: mm_create(struct mm_master *mmalloc, size_t size)
76: {
77: void *address;
78: struct mm_master *mm;
79:
80: if (mmalloc == NULL)
81: mm = xmalloc(sizeof(struct mm_master));
82: else
83: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
84:
1.3 markus 85: /*
1.1 provos 86: * If the memory map has a mm_master it can be completely
87: * shared including authentication between the child
88: * and the client.
89: */
90: mm->mmalloc = mmalloc;
91:
92: address = mmap(NULL, size, PROT_WRITE|PROT_READ, MAP_ANON|MAP_SHARED,
93: -1, 0);
94: if (address == MAP_FAILED)
1.5 stevesk 95: fatal("mmap(%lu): %s", (u_long)size, strerror(errno));
1.1 provos 96:
97: mm->address = address;
98: mm->size = size;
99:
100: RB_INIT(&mm->rb_free);
101: RB_INIT(&mm->rb_allocated);
102:
103: mm_make_entry(mm, &mm->rb_free, address, size);
104:
105: return (mm);
106: }
107:
108: /* Frees either the allocated or the free list */
109:
1.2 markus 110: static void
1.1 provos 111: mm_freelist(struct mm_master *mmalloc, struct mmtree *head)
112: {
113: struct mm_share *mms, *next;
114:
115: for (mms = RB_ROOT(head); mms; mms = next) {
116: next = RB_NEXT(mmtree, head, mms);
117: RB_REMOVE(mmtree, head, mms);
118: if (mmalloc == NULL)
119: xfree(mms);
120: else
121: mm_free(mmalloc, mms);
122: }
123: }
124:
125: /* Destroys a memory mapped area */
126:
127: void
128: mm_destroy(struct mm_master *mm)
129: {
130: mm_freelist(mm->mmalloc, &mm->rb_free);
131: mm_freelist(mm->mmalloc, &mm->rb_allocated);
132:
133: if (munmap(mm->address, mm->size) == -1)
1.5 stevesk 134: fatal("munmap(%p, %lu): %s", mm->address, (u_long)mm->size,
135: strerror(errno));
1.1 provos 136: if (mm->mmalloc == NULL)
137: xfree(mm);
138: else
139: mm_free(mm->mmalloc, mm);
140: }
141:
142: void *
143: mm_xmalloc(struct mm_master *mm, size_t size)
144: {
145: void *address;
146:
147: address = mm_malloc(mm, size);
148: if (address == NULL)
1.6 markus 149: fatal("%s: mm_malloc(%lu)", __func__, (u_long)size);
1.1 provos 150: return (address);
151: }
152:
153:
154: /* Allocates data from a memory mapped area */
155:
156: void *
157: mm_malloc(struct mm_master *mm, size_t size)
158: {
159: struct mm_share *mms, *tmp;
160:
161: if (size == 0)
162: fatal("mm_malloc: try to allocate 0 space");
163:
164: size = ((size + MM_MINSIZE - 1) / MM_MINSIZE) * MM_MINSIZE;
165:
166: RB_FOREACH(mms, mmtree, &mm->rb_free) {
167: if (mms->size >= size)
168: break;
169: }
170:
171: if (mms == NULL)
172: return (NULL);
173:
1.3 markus 174: /* Debug */
1.1 provos 175: memset(mms->address, 0xd0, size);
176:
177: tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size);
178:
179: /* Does not change order in RB tree */
180: mms->size -= size;
181: mms->address = (u_char *)mms->address + size;
182:
183: if (mms->size == 0) {
184: RB_REMOVE(mmtree, &mm->rb_free, mms);
185: if (mm->mmalloc == NULL)
186: xfree(mms);
187: else
188: mm_free(mm->mmalloc, mms);
189: }
190:
191: return (tmp->address);
192: }
193:
194: /* Frees memory in a memory mapped area */
195:
196: void
197: mm_free(struct mm_master *mm, void *address)
198: {
199: struct mm_share *mms, *prev, tmp;
200:
201: tmp.address = address;
202: mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp);
203: if (mms == NULL)
204: fatal("mm_free(%p): can not find %p", mm, address);
205:
1.3 markus 206: /* Debug */
1.1 provos 207: memset(mms->address, 0xd0, mms->size);
208:
209: /* Remove from allocated list and insert in free list */
210: RB_REMOVE(mmtree, &mm->rb_allocated, mms);
211: if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL)
212: fatal("mm_free(%p): double address %p", mm, address);
213:
214: /* Find previous entry */
215: prev = mms;
216: if (RB_LEFT(prev, next)) {
217: prev = RB_LEFT(prev, next);
218: while (RB_RIGHT(prev, next))
219: prev = RB_RIGHT(prev, next);
220: } else {
221: if (RB_PARENT(prev, next) &&
222: (prev == RB_RIGHT(RB_PARENT(prev, next), next)))
223: prev = RB_PARENT(prev, next);
224: else {
225: while (RB_PARENT(prev, next) &&
226: (prev == RB_LEFT(RB_PARENT(prev, next), next)))
227: prev = RB_PARENT(prev, next);
228: prev = RB_PARENT(prev, next);
229: }
230: }
231:
232: /* Check if range does not overlap */
233: if (prev != NULL && MM_ADDRESS_END(prev) > address)
1.4 stevesk 234: fatal("mm_free: memory corruption: %p(%lu) > %p",
235: prev->address, (u_long)prev->size, address);
1.1 provos 236:
237: /* See if we can merge backwards */
238: if (prev != NULL && MM_ADDRESS_END(prev) == address) {
239: prev->size += mms->size;
240: RB_REMOVE(mmtree, &mm->rb_free, mms);
241: if (mm->mmalloc == NULL)
242: xfree(mms);
243: else
244: mm_free(mm->mmalloc, mms);
245: } else
246: prev = mms;
247:
248: if (prev == NULL)
249: return;
250:
251: /* Check if we can merge forwards */
252: mms = RB_NEXT(mmtree, &mm->rb_free, prev);
253: if (mms == NULL)
254: return;
255:
256: if (MM_ADDRESS_END(prev) > mms->address)
1.4 stevesk 257: fatal("mm_free: memory corruption: %p < %p(%lu)",
258: mms->address, prev->address, (u_long)prev->size);
1.1 provos 259: if (MM_ADDRESS_END(prev) != mms->address)
260: return;
261:
262: prev->size += mms->size;
263: RB_REMOVE(mmtree, &mm->rb_free, mms);
264:
265: if (mm->mmalloc == NULL)
266: xfree(mms);
267: else
268: mm_free(mm->mmalloc, mms);
269: }
270:
1.2 markus 271: static void
1.1 provos 272: mm_sync_list(struct mmtree *oldtree, struct mmtree *newtree,
273: struct mm_master *mm, struct mm_master *mmold)
274: {
275: struct mm_master *mmalloc = mm->mmalloc;
276: struct mm_share *mms, *new;
277:
278: /* Sync free list */
279: RB_FOREACH(mms, mmtree, oldtree) {
280: /* Check the values */
281: mm_memvalid(mmold, mms, sizeof(struct mm_share));
282: mm_memvalid(mm, mms->address, mms->size);
283:
284: new = mm_xmalloc(mmalloc, sizeof(struct mm_share));
285: memcpy(new, mms, sizeof(struct mm_share));
286: RB_INSERT(mmtree, newtree, new);
287: }
288: }
289:
290: void
291: mm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc)
292: {
293: struct mm_master *mm;
294: struct mm_master *mmalloc;
295: struct mm_master *mmold;
296: struct mmtree rb_free, rb_allocated;
297:
1.6 markus 298: debug3("%s: Share sync", __func__);
1.1 provos 299:
300: mm = *pmm;
301: mmold = mm->mmalloc;
302: mm_memvalid(mmold, mm, sizeof(*mm));
303:
304: mmalloc = mm_create(NULL, mm->size);
305: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
306: memcpy(mm, *pmm, sizeof(struct mm_master));
307: mm->mmalloc = mmalloc;
308:
309: rb_free = mm->rb_free;
310: rb_allocated = mm->rb_allocated;
311:
312: RB_INIT(&mm->rb_free);
313: RB_INIT(&mm->rb_allocated);
314:
315: mm_sync_list(&rb_free, &mm->rb_free, mm, mmold);
316: mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold);
317:
318: mm_destroy(mmold);
319:
320: *pmm = mm;
321: *pmmalloc = mmalloc;
322:
1.6 markus 323: debug3("%s: Share sync end", __func__);
1.1 provos 324: }
325:
326: void
327: mm_memvalid(struct mm_master *mm, void *address, size_t size)
328: {
329: void *end = (u_char *)address + size;
330:
331: if (address < mm->address)
332: fatal("mm_memvalid: address too small: %p", address);
333: if (end < address)
334: fatal("mm_memvalid: end < address: %p < %p", end, address);
335: if (end > (void *)((u_char *)mm->address + mm->size))
336: fatal("mm_memvalid: address too large: %p", address);
337: }