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