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