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