Annotation of src/usr.bin/ssh/monitor_mm.c, Revision 1.18
1.18 ! djm 1: /* $OpenBSD: monitor_mm.c,v 1.17 2013/05/17 00:13:13 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:
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)
1.18 ! djm 64: tmp = xcalloc(1, sizeof(struct mm_share));
1.1 provos 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)
1.18 ! djm 87: mm = xcalloc(1, sizeof(struct mm_master));
1.1 provos 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.18 ! djm 156: memset(address, 0, size);
1.1 provos 157: return (address);
158: }
159:
160:
161: /* Allocates data from a memory mapped area */
162:
163: void *
164: mm_malloc(struct mm_master *mm, size_t size)
165: {
166: struct mm_share *mms, *tmp;
167:
168: if (size == 0)
169: fatal("mm_malloc: try to allocate 0 space");
1.8 millert 170: if (size > SIZE_T_MAX - MM_MINSIZE + 1)
171: fatal("mm_malloc: size too big");
1.1 provos 172:
1.8 millert 173: size = ((size + (MM_MINSIZE - 1)) / MM_MINSIZE) * MM_MINSIZE;
1.1 provos 174:
175: RB_FOREACH(mms, mmtree, &mm->rb_free) {
176: if (mms->size >= size)
177: break;
178: }
179:
180: if (mms == NULL)
181: return (NULL);
182:
1.3 markus 183: /* Debug */
1.1 provos 184: memset(mms->address, 0xd0, size);
185:
186: tmp = mm_make_entry(mm, &mm->rb_allocated, mms->address, size);
187:
188: /* Does not change order in RB tree */
189: mms->size -= size;
190: mms->address = (u_char *)mms->address + size;
191:
192: if (mms->size == 0) {
193: RB_REMOVE(mmtree, &mm->rb_free, mms);
194: if (mm->mmalloc == NULL)
1.17 djm 195: free(mms);
1.1 provos 196: else
197: mm_free(mm->mmalloc, mms);
198: }
199:
200: return (tmp->address);
201: }
202:
203: /* Frees memory in a memory mapped area */
204:
205: void
206: mm_free(struct mm_master *mm, void *address)
207: {
208: struct mm_share *mms, *prev, tmp;
209:
210: tmp.address = address;
211: mms = RB_FIND(mmtree, &mm->rb_allocated, &tmp);
212: if (mms == NULL)
213: fatal("mm_free(%p): can not find %p", mm, address);
214:
1.3 markus 215: /* Debug */
1.1 provos 216: memset(mms->address, 0xd0, mms->size);
217:
218: /* Remove from allocated list and insert in free list */
219: RB_REMOVE(mmtree, &mm->rb_allocated, mms);
220: if (RB_INSERT(mmtree, &mm->rb_free, mms) != NULL)
221: fatal("mm_free(%p): double address %p", mm, address);
222:
223: /* Find previous entry */
224: prev = mms;
225: if (RB_LEFT(prev, next)) {
226: prev = RB_LEFT(prev, next);
227: while (RB_RIGHT(prev, next))
228: prev = RB_RIGHT(prev, next);
229: } else {
230: if (RB_PARENT(prev, next) &&
231: (prev == RB_RIGHT(RB_PARENT(prev, next), next)))
232: prev = RB_PARENT(prev, next);
233: else {
234: while (RB_PARENT(prev, next) &&
235: (prev == RB_LEFT(RB_PARENT(prev, next), next)))
236: prev = RB_PARENT(prev, next);
237: prev = RB_PARENT(prev, next);
238: }
239: }
240:
241: /* Check if range does not overlap */
242: if (prev != NULL && MM_ADDRESS_END(prev) > address)
1.4 stevesk 243: fatal("mm_free: memory corruption: %p(%lu) > %p",
244: prev->address, (u_long)prev->size, address);
1.1 provos 245:
246: /* See if we can merge backwards */
247: if (prev != NULL && MM_ADDRESS_END(prev) == address) {
248: prev->size += mms->size;
249: RB_REMOVE(mmtree, &mm->rb_free, mms);
250: if (mm->mmalloc == NULL)
1.17 djm 251: free(mms);
1.1 provos 252: else
253: mm_free(mm->mmalloc, mms);
254: } else
255: prev = mms;
256:
257: if (prev == NULL)
258: return;
259:
260: /* Check if we can merge forwards */
261: mms = RB_NEXT(mmtree, &mm->rb_free, prev);
262: if (mms == NULL)
263: return;
264:
265: if (MM_ADDRESS_END(prev) > mms->address)
1.4 stevesk 266: fatal("mm_free: memory corruption: %p < %p(%lu)",
267: mms->address, prev->address, (u_long)prev->size);
1.1 provos 268: if (MM_ADDRESS_END(prev) != mms->address)
269: return;
270:
271: prev->size += mms->size;
272: RB_REMOVE(mmtree, &mm->rb_free, mms);
273:
274: if (mm->mmalloc == NULL)
1.17 djm 275: free(mms);
1.1 provos 276: else
277: mm_free(mm->mmalloc, mms);
278: }
279:
1.2 markus 280: static void
1.1 provos 281: mm_sync_list(struct mmtree *oldtree, struct mmtree *newtree,
282: struct mm_master *mm, struct mm_master *mmold)
283: {
284: struct mm_master *mmalloc = mm->mmalloc;
285: struct mm_share *mms, *new;
286:
287: /* Sync free list */
288: RB_FOREACH(mms, mmtree, oldtree) {
289: /* Check the values */
290: mm_memvalid(mmold, mms, sizeof(struct mm_share));
291: mm_memvalid(mm, mms->address, mms->size);
292:
293: new = mm_xmalloc(mmalloc, sizeof(struct mm_share));
294: memcpy(new, mms, sizeof(struct mm_share));
295: RB_INSERT(mmtree, newtree, new);
296: }
297: }
298:
299: void
300: mm_share_sync(struct mm_master **pmm, struct mm_master **pmmalloc)
301: {
302: struct mm_master *mm;
303: struct mm_master *mmalloc;
304: struct mm_master *mmold;
305: struct mmtree rb_free, rb_allocated;
306:
1.6 markus 307: debug3("%s: Share sync", __func__);
1.1 provos 308:
309: mm = *pmm;
310: mmold = mm->mmalloc;
311: mm_memvalid(mmold, mm, sizeof(*mm));
312:
313: mmalloc = mm_create(NULL, mm->size);
314: mm = mm_xmalloc(mmalloc, sizeof(struct mm_master));
315: memcpy(mm, *pmm, sizeof(struct mm_master));
316: mm->mmalloc = mmalloc;
317:
318: rb_free = mm->rb_free;
319: rb_allocated = mm->rb_allocated;
320:
321: RB_INIT(&mm->rb_free);
322: RB_INIT(&mm->rb_allocated);
323:
324: mm_sync_list(&rb_free, &mm->rb_free, mm, mmold);
325: mm_sync_list(&rb_allocated, &mm->rb_allocated, mm, mmold);
326:
327: mm_destroy(mmold);
328:
329: *pmm = mm;
330: *pmmalloc = mmalloc;
331:
1.6 markus 332: debug3("%s: Share sync end", __func__);
1.1 provos 333: }
334:
335: void
336: mm_memvalid(struct mm_master *mm, void *address, size_t size)
337: {
338: void *end = (u_char *)address + size;
339:
340: if (address < mm->address)
341: fatal("mm_memvalid: address too small: %p", address);
342: if (end < address)
343: fatal("mm_memvalid: end < address: %p < %p", end, address);
344: if (end > (void *)((u_char *)mm->address + mm->size))
345: fatal("mm_memvalid: address too large: %p", address);
346: }