2 * Tiny C Memory and bounds checker
4 * Copyright (c) 2002 Fabrice Bellard
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
28 /* define so that bound array is static (faster, but use memory if
29 bound checking not used) */
30 //#define BOUND_STATIC
32 /* use malloc hooks. Currently the code cannot be reliable if no hooks */
33 #define CONFIG_TCC_MALLOC_HOOKS
35 #define BOUND_T1_BITS 13
36 #define BOUND_T2_BITS 11
37 #define BOUND_T3_BITS (32 - BOUND_T1_BITS - BOUND_T2_BITS)
39 #define BOUND_T1_SIZE (1 << BOUND_T1_BITS)
40 #define BOUND_T2_SIZE (1 << BOUND_T2_BITS)
41 #define BOUND_T3_SIZE (1 << BOUND_T3_BITS)
42 #define BOUND_E_BITS 4
44 #define BOUND_T23_BITS (BOUND_T2_BITS + BOUND_T3_BITS)
45 #define BOUND_T23_SIZE (1 << BOUND_T23_BITS)
48 /* this pointer is generated when bound check is incorrect */
49 #define INVALID_POINTER ((void *)(-2))
50 /* size of an empty region */
51 #define EMPTY_SIZE 0xffffffff
52 /* size of an invalid region */
53 #define INVALID_SIZE 0
55 typedef struct BoundEntry
{
58 struct BoundEntry
*next
;
59 unsigned long is_invalid
; /* true if pointers outside region are invalid */
62 /* external interface */
63 void __bound_init(void);
64 void __bound_new_region(void *p
, unsigned long size
);
65 int __bound_delete_region(void *p
);
67 /* currently, tcc cannot compile that because we use unsupported GNU C
69 #if !defined(__TINYC__)
70 void *__bound_ptr_add(void *p
, int offset
) __attribute__((regparm(2)));
71 void *__bound_ptr_indir1(void *p
, int offset
) __attribute__((regparm(2)));
72 void *__bound_ptr_indir2(void *p
, int offset
) __attribute__((regparm(2)));
73 void *__bound_ptr_indir4(void *p
, int offset
) __attribute__((regparm(2)));
74 void *__bound_ptr_indir8(void *p
, int offset
) __attribute__((regparm(2)));
75 void *__bound_ptr_indir12(void *p
, int offset
) __attribute__((regparm(2)));
76 void *__bound_ptr_indir16(void *p
, int offset
) __attribute__((regparm(2)));
77 void __bound_local_new(void *p
) __attribute__((regparm(1)));
78 void __bound_local_delete(void *p
) __attribute__((regparm(1)));
80 static void *get_caller_pc(int n
);
82 void *__bound_malloc(size_t size
, const void *caller
);
83 void *__bound_memalign(size_t size
, size_t align
, const void *caller
);
84 void __bound_free(void *ptr
, const void *caller
);
85 void *__bound_realloc(void *ptr
, size_t size
, const void *caller
);
86 static void *libc_malloc(size_t size
);
87 static void libc_free(void *ptr
);
88 static void install_malloc_hooks(void);
89 static void restore_malloc_hooks(void);
91 #ifdef CONFIG_TCC_MALLOC_HOOKS
92 static void *saved_malloc_hook
;
93 static void *saved_free_hook
;
94 static void *saved_realloc_hook
;
95 static void *saved_memalign_hook
;
101 extern char __bounds_start
; /* start of static bounds table */
102 /* runtime error output */
103 extern void rt_error(unsigned long pc
, const char *fmt
, ...);
106 static BoundEntry
*__bound_t1
[BOUND_T1_SIZE
]; /* page table */
108 static BoundEntry
**__bound_t1
; /* page table */
110 static BoundEntry
*__bound_empty_t2
; /* empty page, for unused pages */
111 static BoundEntry
*__bound_invalid_t2
; /* invalid page, for invalid pointers */
113 static BoundEntry
*__bound_find_region(BoundEntry
*e1
, void *p
)
115 unsigned long addr
, tmp
;
120 addr
= (unsigned long)p
;
122 if (addr
<= e
->size
) {
123 /* put region at the head */
125 e1
->start
= e
->start
;
134 /* no entry found: return empty entry or invalid entry */
136 return __bound_invalid_t2
;
138 return __bound_empty_t2
;
141 /* print a bound error message */
142 static void bound_error(const void *caller
, const char *fmt
, ...)
144 rt_error((unsigned long)caller
, "%s", fmt
);
147 static void bound_alloc_error(void)
149 bound_error(NULL
, "not enough memory for bound checking code");
152 /* currently, tcc cannot compile that because we use GNUC extensions */
153 #if !defined(__TINYC__)
155 /* return '(p + offset)' for pointer arithmetic (a pointer can reach
156 the end of a region in this case */
157 void *__bound_ptr_add(void *p
, int offset
)
159 unsigned long addr
= (unsigned long)p
;
161 #if defined(BOUND_DEBUG)
162 printf("add: 0x%x %d\n", (int)p
, offset
);
165 e
= __bound_t1
[addr
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
)];
166 e
= (BoundEntry
*)((char *)e
+
167 ((addr
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
168 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
)));
170 if (addr
> e
->size
) {
171 e
= __bound_find_region(e
, p
);
172 addr
= (unsigned long)p
- e
->start
;
176 return INVALID_POINTER
; /* return an invalid pointer */
180 /* return '(p + offset)' for pointer indirection (the resulting must
181 be strictly inside the region */
182 #define BOUND_PTR_INDIR(dsize) \
183 void *__bound_ptr_indir ## dsize (void *p, int offset) \
185 unsigned long addr = (unsigned long)p; \
188 e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)]; \
189 e = (BoundEntry *)((char *)e + \
190 ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) & \
191 ((BOUND_T2_SIZE - 1) << BOUND_E_BITS))); \
193 if (addr > e->size) { \
194 e = __bound_find_region(e, p); \
195 addr = (unsigned long)p - e->start; \
197 addr += offset + dsize; \
198 if (addr > e->size) \
199 return INVALID_POINTER; /* return an invalid pointer */ \
205 /* return the PC of the N'th caller (N=1: first caller) */
206 static void *get_caller_pc(int n
)
211 __asm__
__volatile__ ("movl %%ebp,%0" :"=g" (fp
));
213 fp
= ((unsigned long *)fp
)[0];
214 return ((void **)fp
)[1];
217 /* return the frame pointer of the caller */
218 #define GET_CALLER_FP(fp)\
221 __asm__ __volatile__ ("movl %%ebp,%0" :"=g" (fp1));\
225 #error put code to extract the calling frame pointer
228 /* called when entering a function to add all the local regions */
229 void __bound_local_new(void *p1
)
231 unsigned long addr
, size
, fp
, *p
= p1
;
240 __bound_new_region((void *)addr
, size
);
244 /* called when leaving a function to delete all the local regions */
245 void __bound_local_delete(void *p1
)
247 unsigned long addr
, fp
, *p
= p1
;
255 __bound_delete_region((void *)addr
);
261 void __bound_local_new(void *p
)
264 void __bound_local_delete(void *p
)
268 void *__bound_ptr_add(void *p
, int offset
)
273 #define BOUND_PTR_INDIR(dsize) \
274 void *__bound_ptr_indir ## dsize (void *p, int offset) \
279 static void *get_caller_pc(int n
)
292 static BoundEntry
*__bound_new_page(void)
297 page
= libc_malloc(sizeof(BoundEntry
) * BOUND_T2_SIZE
);
300 for(i
=0;i
<BOUND_T2_SIZE
;i
++) {
301 /* put empty entries */
303 page
[i
].size
= EMPTY_SIZE
;
305 page
[i
].is_invalid
= 0;
310 /* currently we use malloc(). Should use bound_new_page() */
311 static BoundEntry
*bound_new_entry(void)
314 e
= libc_malloc(sizeof(BoundEntry
));
318 static void bound_free_entry(BoundEntry
*e
)
323 static inline BoundEntry
*get_page(int index
)
326 page
= __bound_t1
[index
];
327 if (page
== __bound_empty_t2
|| page
== __bound_invalid_t2
) {
328 /* create a new page if necessary */
329 page
= __bound_new_page();
330 __bound_t1
[index
] = page
;
335 /* mark a region as being invalid (can only be used during init) */
336 static void mark_invalid(unsigned long addr
, unsigned long size
)
338 unsigned long start
, end
;
340 int t1_start
, t1_end
, i
, j
, t2_start
, t2_end
;
345 t2_start
= (start
+ BOUND_T3_SIZE
- 1) >> BOUND_T3_BITS
;
347 t2_end
= end
>> BOUND_T3_BITS
;
349 t2_end
= 1 << (BOUND_T1_BITS
+ BOUND_T2_BITS
);
352 printf("mark_invalid: start = %x %x\n", t2_start
, t2_end
);
355 /* first we handle full pages */
356 t1_start
= (t2_start
+ BOUND_T2_SIZE
- 1) >> BOUND_T2_BITS
;
357 t1_end
= t2_end
>> BOUND_T2_BITS
;
359 i
= t2_start
& (BOUND_T2_SIZE
- 1);
360 j
= t2_end
& (BOUND_T2_SIZE
- 1);
362 if (t1_start
== t1_end
) {
363 page
= get_page(t2_start
>> BOUND_T2_BITS
);
365 page
[i
].size
= INVALID_SIZE
;
366 page
[i
].is_invalid
= 1;
370 page
= get_page(t2_start
>> BOUND_T2_BITS
);
371 for(; i
< BOUND_T2_SIZE
; i
++) {
372 page
[i
].size
= INVALID_SIZE
;
373 page
[i
].is_invalid
= 1;
376 for(i
= t1_start
; i
< t1_end
; i
++) {
377 __bound_t1
[i
] = __bound_invalid_t2
;
380 page
= get_page(t1_end
);
381 for(i
= 0; i
< j
; i
++) {
382 page
[i
].size
= INVALID_SIZE
;
383 page
[i
].is_invalid
= 1;
389 void __bound_init(void)
393 unsigned long start
, size
;
396 /* save malloc hooks and install bound check hooks */
397 install_malloc_hooks();
400 __bound_t1
= libc_malloc(BOUND_T1_SIZE
* sizeof(BoundEntry
*));
404 __bound_empty_t2
= __bound_new_page();
405 for(i
=0;i
<BOUND_T1_SIZE
;i
++) {
406 __bound_t1
[i
] = __bound_empty_t2
;
409 page
= __bound_new_page();
410 for(i
=0;i
<BOUND_T2_SIZE
;i
++) {
411 /* put invalid entries */
413 page
[i
].size
= INVALID_SIZE
;
415 page
[i
].is_invalid
= 1;
417 __bound_invalid_t2
= page
;
419 /* invalid pointer zone */
420 start
= (unsigned long)INVALID_POINTER
& ~(BOUND_T23_SIZE
- 1);
421 size
= BOUND_T23_SIZE
;
422 mark_invalid(start
, size
);
424 #if !defined(__TINYC__) && defined(CONFIG_TCC_MALLOC_HOOKS)
425 /* malloc zone is also marked invalid. can only use that with
426 hooks because all libs should use the same malloc. The solution
427 would be to build a new malloc for tcc. */
428 start
= (unsigned long)&_end
;
429 size
= 128 * 0x100000;
430 mark_invalid(start
, size
);
433 /* add all static bound check values */
434 p
= (int *)&__bounds_start
;
436 __bound_new_region((void *)p
[0], p
[1]);
441 static inline void add_region(BoundEntry
*e
,
442 unsigned long start
, unsigned long size
)
446 /* no region : add it */
450 /* already regions in the list: add it at the head */
451 e1
= bound_new_entry();
452 e1
->start
= e
->start
;
461 /* create a new region. It should not already exist in the region list */
462 void __bound_new_region(void *p
, unsigned long size
)
464 unsigned long start
, end
;
465 BoundEntry
*page
, *e
, *e2
;
466 int t1_start
, t1_end
, i
, t2_start
, t2_end
;
468 start
= (unsigned long)p
;
470 t1_start
= start
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
);
471 t1_end
= end
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
);
474 page
= get_page(t1_start
);
475 t2_start
= (start
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
476 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
);
477 t2_end
= (end
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
478 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
);
480 printf("new %lx %lx %x %x %x %x\n",
481 start
, end
, t1_start
, t1_end
, t2_start
, t2_end
);
484 e
= (BoundEntry
*)((char *)page
+ t2_start
);
485 add_region(e
, start
, size
);
487 if (t1_end
== t1_start
) {
488 /* same ending page */
489 e2
= (BoundEntry
*)((char *)page
+ t2_end
);
496 add_region(e
, start
, size
);
499 /* mark until end of page */
500 e2
= page
+ BOUND_T2_SIZE
;
506 /* mark intermediate pages, if any */
507 for(i
=t1_start
+1;i
<t1_end
;i
++) {
509 e2
= page
+ BOUND_T2_SIZE
;
510 for(e
=page
;e
<e2
;e
++) {
516 page
= get_page(t1_end
);
517 e2
= (BoundEntry
*)((char *)page
+ t2_end
);
518 for(e
=page
;e
<e2
;e
++) {
522 add_region(e
, start
, size
);
526 /* delete a region */
527 static inline void delete_region(BoundEntry
*e
,
528 void *p
, unsigned long empty_size
)
533 addr
= (unsigned long)p
;
535 if (addr
<= e
->size
) {
536 /* region found is first one */
539 /* no more region: mark it empty */
541 e
->size
= empty_size
;
543 /* copy next region in head */
544 e
->start
= e1
->start
;
547 bound_free_entry(e1
);
550 /* find the matching region */
554 /* region not found: do nothing */
557 addr
= (unsigned long)p
- e
->start
;
558 if (addr
<= e
->size
) {
559 /* found: remove entry */
568 /* WARNING: 'p' must be the starting point of the region. */
569 /* return non zero if error */
570 int __bound_delete_region(void *p
)
572 unsigned long start
, end
, addr
, size
, empty_size
;
573 BoundEntry
*page
, *e
, *e2
;
574 int t1_start
, t1_end
, t2_start
, t2_end
, i
;
576 start
= (unsigned long)p
;
577 t1_start
= start
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
);
578 t2_start
= (start
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
579 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
);
581 /* find region size */
582 page
= __bound_t1
[t1_start
];
583 e
= (BoundEntry
*)((char *)page
+ t2_start
);
584 addr
= start
- e
->start
;
586 e
= __bound_find_region(e
, p
);
587 /* test if invalid region */
588 if (e
->size
== EMPTY_SIZE
|| (unsigned long)p
!= e
->start
)
590 /* compute the size we put in invalid regions */
592 empty_size
= INVALID_SIZE
;
594 empty_size
= EMPTY_SIZE
;
598 /* now we can free each entry */
599 t1_end
= end
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
);
600 t2_end
= (end
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
601 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
);
603 delete_region(e
, p
, empty_size
);
604 if (t1_end
== t1_start
) {
605 /* same ending page */
606 e2
= (BoundEntry
*)((char *)page
+ t2_end
);
611 e
->size
= empty_size
;
613 delete_region(e
, p
, empty_size
);
616 /* mark until end of page */
617 e2
= page
+ BOUND_T2_SIZE
;
621 e
->size
= empty_size
;
623 /* mark intermediate pages, if any */
624 /* XXX: should free them */
625 for(i
=t1_start
+1;i
<t1_end
;i
++) {
627 e2
= page
+ BOUND_T2_SIZE
;
628 for(e
=page
;e
<e2
;e
++) {
630 e
->size
= empty_size
;
634 page
= get_page(t2_end
);
635 e2
= (BoundEntry
*)((char *)page
+ t2_end
);
636 for(e
=page
;e
<e2
;e
++) {
638 e
->size
= empty_size
;
640 delete_region(e
, p
, empty_size
);
645 /* return the size of the region starting at p, or EMPTY_SIZE if non
647 static unsigned long get_region_size(void *p
)
649 unsigned long addr
= (unsigned long)p
;
652 e
= __bound_t1
[addr
>> (BOUND_T2_BITS
+ BOUND_T3_BITS
)];
653 e
= (BoundEntry
*)((char *)e
+
654 ((addr
>> (BOUND_T3_BITS
- BOUND_E_BITS
)) &
655 ((BOUND_T2_SIZE
- 1) << BOUND_E_BITS
)));
658 e
= __bound_find_region(e
, p
);
659 if (e
->start
!= (unsigned long)p
)
664 /* patched memory functions */
666 static void install_malloc_hooks(void)
668 #ifdef CONFIG_TCC_MALLOC_HOOKS
669 saved_malloc_hook
= __malloc_hook
;
670 saved_free_hook
= __free_hook
;
671 saved_realloc_hook
= __realloc_hook
;
672 saved_memalign_hook
= __memalign_hook
;
673 __malloc_hook
= __bound_malloc
;
674 __free_hook
= __bound_free
;
675 __realloc_hook
= __bound_realloc
;
676 __memalign_hook
= __bound_memalign
;
680 static void restore_malloc_hooks(void)
682 #ifdef CONFIG_TCC_MALLOC_HOOKS
683 __malloc_hook
= saved_malloc_hook
;
684 __free_hook
= saved_free_hook
;
685 __realloc_hook
= saved_realloc_hook
;
686 __memalign_hook
= saved_memalign_hook
;
690 static void *libc_malloc(size_t size
)
693 restore_malloc_hooks();
695 install_malloc_hooks();
699 static void libc_free(void *ptr
)
701 restore_malloc_hooks();
703 install_malloc_hooks();
706 /* XXX: we should use a malloc which ensure that it is unlikely that
707 two malloc'ed data have the same address if 'free' are made in
709 void *__bound_malloc(size_t size
, const void *caller
)
713 /* we allocate one more byte to ensure the regions will be
714 separated by at least one byte. With the glibc malloc, it may
715 be in fact not necessary */
716 ptr
= libc_malloc(size
+ 1);
720 __bound_new_region(ptr
, size
);
724 void *__bound_memalign(size_t size
, size_t align
, const void *caller
)
728 restore_malloc_hooks();
730 /* we allocate one more byte to ensure the regions will be
731 separated by at least one byte. With the glibc malloc, it may
732 be in fact not necessary */
733 ptr
= memalign(size
+ 1, align
);
735 install_malloc_hooks();
739 __bound_new_region(ptr
, size
);
743 void __bound_free(void *ptr
, const void *caller
)
747 if (__bound_delete_region(ptr
) != 0)
748 bound_error(caller
, "freeing invalid region");
753 void *__bound_realloc(void *ptr
, size_t size
, const void *caller
)
759 __bound_free(ptr
, caller
);
762 ptr1
= __bound_malloc(size
, caller
);
763 if (ptr
== NULL
|| ptr1
== NULL
)
765 old_size
= get_region_size(ptr
);
766 if (old_size
== EMPTY_SIZE
)
767 bound_error(caller
, "realloc'ing invalid pointer");
768 memcpy(ptr1
, ptr
, old_size
);
769 __bound_free(ptr
, caller
);
774 #ifndef CONFIG_TCC_MALLOC_HOOKS
775 void *__bound_calloc(size_t nmemb
, size_t size
)
779 ptr
= __bound_malloc(size
);
782 memset(ptr
, 0, size
);
788 static void bound_dump(void)
790 BoundEntry
*page
, *e
;
793 printf("region dump:\n");
794 for(i
=0;i
<BOUND_T1_SIZE
;i
++) {
795 page
= __bound_t1
[i
];
796 for(j
=0;j
<BOUND_T2_SIZE
;j
++) {
798 /* do not print invalid or empty entries */
799 if (e
->size
!= EMPTY_SIZE
&& e
->start
!= 0) {
801 (i
<< (BOUND_T2_BITS
+ BOUND_T3_BITS
)) +
802 (j
<< BOUND_T3_BITS
));
804 printf(" %08lx:%08lx", e
->start
, e
->start
+ e
->size
);
814 /* some useful checked functions */
816 /* check that (p ... p + size - 1) lies inside 'p' region, if any */
817 static void __bound_check(const void *p
, size_t size
)
821 p
= __bound_ptr_add((void *)p
, size
);
822 if (p
== INVALID_POINTER
)
823 bound_error(get_caller_pc(2), "invalid pointer");
826 void *__bound_memcpy(void *dst
, const void *src
, size_t size
)
828 __bound_check(dst
, size
);
829 __bound_check(src
, size
);
830 /* check also region overlap */
831 if (src
>= dst
&& src
< dst
+ size
)
832 bound_error(get_caller_pc(1), "overlapping regions in memcpy()");
833 return memcpy(dst
, src
, size
);
836 void *__bound_memmove(void *dst
, const void *src
, size_t size
)
838 __bound_check(dst
, size
);
839 __bound_check(src
, size
);
840 return memmove(dst
, src
, size
);
843 void *__bound_memset(void *dst
, int c
, size_t size
)
845 __bound_check(dst
, size
);
846 return memset(dst
, c
, size
);
849 /* XXX: could be optimized */
850 int __bound_strlen(const char *s
)
857 p
= __bound_ptr_indir1((char *)s
, len
);
858 if (p
== INVALID_POINTER
)
859 bound_error(get_caller_pc(1), "bad pointer in strlen()");
867 char *__bound_strcpy(char *dst
, const char *src
)
870 len
= __bound_strlen(src
);
871 return __bound_memcpy(dst
, src
, len
+ 1);