2 * Tiny C Memory and bounds checker
4 * Copyright (c) 2002 Fabrice Bellard
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
11 * This library 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 GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 #if !defined(__FreeBSD__) \
27 && !defined(__FreeBSD_kernel__) \
28 && !defined(__DragonFly__) \
29 && !defined(__OpenBSD__) \
30 && !defined(__APPLE__) \
31 && !defined(__NetBSD__)
37 #include <sys/syscall.h>
40 #define BOUND_DEBUG (1)
41 #define BOUND_STATISTIC (1)
44 #define dprintf(a...) if (print_calls) fprintf(a)
50 /* an __attribute__ macro is defined in the system headers */
53 #define FASTCALL __attribute__((regparm(3)))
56 # define DLL_EXPORT __declspec(dllexport)
61 #if defined(__FreeBSD__) \
62 || defined(__FreeBSD_kernel__) \
63 || defined(__DragonFly__) \
64 || defined(__OpenBSD__) \
65 || defined(__NetBSD__) \
66 || defined(__dietlibc__)
72 #define HAVE_MEMALIGN (0)
73 #define HAS_ENVIRON (0)
74 #define MALLOC_REDIR (0)
75 #define HAVE_PTHREAD_CREATE (0)
76 #define HAVE_CTYPE (0)
77 #define HAVE_ERRNO (0)
82 static CRITICAL_SECTION bounds_sem
;
83 #define INIT_SEM() InitializeCriticalSection(&bounds_sem)
84 #define EXIT_SEM() DeleteCriticalSection(&bounds_sem)
85 #define WAIT_SEM() EnterCriticalSection(&bounds_sem)
86 #define POST_SEM() LeaveCriticalSection(&bounds_sem)
87 #define HAVE_MEMALIGN (0)
88 #define HAS_ENVIRON (0)
89 #define MALLOC_REDIR (0)
90 #define HAVE_PTHREAD_CREATE (0)
91 #define HAVE_CTYPE (0)
92 #define HAVE_ERRNO (0)
96 #define __USE_GNU /* get RTLD_NEXT */
103 #include <dispatch/dispatch.h>
104 static dispatch_semaphore_t bounds_sem
;
105 #define INIT_SEM() bounds_sem = dispatch_semaphore_create(1)
106 #define EXIT_SEM() dispatch_release(*(dispatch_object_t*)&bounds_sem)
107 #define WAIT_SEM() if (use_sem) dispatch_semaphore_wait(bounds_sem, DISPATCH_TIME_FOREVER)
108 #define POST_SEM() if (use_sem) dispatch_semaphore_signal(bounds_sem)
110 #include <semaphore.h>
111 static sem_t bounds_sem
;
112 #define INIT_SEM() sem_init (&bounds_sem, 0, 1)
113 #define EXIT_SEM() sem_destroy (&bounds_sem)
114 #define WAIT_SEM() if (use_sem) while (sem_wait (&bounds_sem) < 0 \
116 #define POST_SEM() if (use_sem) sem_post (&bounds_sem)
118 static pthread_spinlock_t bounds_spin
;
119 /* about 25% faster then semaphore. */
120 #define INIT_SEM() pthread_spin_init (&bounds_spin, 0)
121 #define EXIT_SEM() pthread_spin_destroy (&bounds_spin)
122 #define WAIT_SEM() if (use_sem) pthread_spin_lock (&bounds_spin)
123 #define POST_SEM() if (use_sem) pthread_spin_unlock (&bounds_spin)
125 #define HAVE_MEMALIGN (1)
126 #define HAS_ENVIRON (1)
127 #define MALLOC_REDIR (1)
128 #define HAVE_PTHREAD_CREATE (1)
129 #define HAVE_CTYPE (1)
130 #define HAVE_ERRNO (1)
132 static void *(*malloc_redir
) (size_t);
133 static void *(*calloc_redir
) (size_t, size_t);
134 static void (*free_redir
) (void *);
135 static void *(*realloc_redir
) (void *, size_t);
136 static void *(*memalign_redir
) (size_t, size_t);
137 static int (*pthread_create_redir
) (pthread_t
*thread
,
138 const pthread_attr_t
*attr
,
139 void *(*start_routine
)(void *), void *arg
);
140 static unsigned int pool_index
;
141 static unsigned char __attribute__((aligned(16))) initial_pool
[256];
142 static unsigned char use_sem
;
146 #define TCC_TYPE_NONE (0)
147 #define TCC_TYPE_MALLOC (1)
148 #define TCC_TYPE_CALLOC (2)
149 #define TCC_TYPE_REALLOC (3)
150 #define TCC_TYPE_MEMALIGN (4)
151 #define TCC_TYPE_STRDUP (5)
153 /* this pointer is generated when bound check is incorrect */
154 #define INVALID_POINTER ((void *)(-2))
156 typedef struct tree_node Tree
;
158 Tree
* left
, * right
;
162 unsigned char is_invalid
; /* true if pointers outside region are invalid */
165 typedef struct alloca_list_struct
{
168 struct alloca_list_struct
*next
;
172 #define BOUND_TID_TYPE DWORD
173 #define BOUND_GET_TID GetCurrentThreadId()
174 #elif defined(__i386__) || defined(__x86_64__) || defined(__arm__) || defined(__aarch64__) || defined(__riscv)
175 #define BOUND_TID_TYPE pid_t
176 #define BOUND_GET_TID syscall (SYS_gettid)
178 #define BOUND_TID_TYPE int
179 #define BOUND_GET_TID 0
182 typedef struct jmp_list_struct
{
187 struct jmp_list_struct
*next
;
190 #define BOUND_STATISTIC_SPLAY (0)
191 static Tree
* splay (size_t addr
, Tree
*t
);
192 static Tree
* splay_end (size_t addr
, Tree
*t
);
193 static Tree
* splay_insert(size_t addr
, size_t size
, Tree
* t
);
194 static Tree
* splay_delete(size_t addr
, Tree
*t
);
195 void splay_printtree(Tree
* t
, int d
);
197 /* external interface */
198 void __bound_checking (int no_check
);
199 void __bound_never_fatal (int no_check
);
200 DLL_EXPORT
void * __bound_ptr_add(void *p
, size_t offset
);
201 DLL_EXPORT
void * __bound_ptr_indir1(void *p
, size_t offset
);
202 DLL_EXPORT
void * __bound_ptr_indir2(void *p
, size_t offset
);
203 DLL_EXPORT
void * __bound_ptr_indir4(void *p
, size_t offset
);
204 DLL_EXPORT
void * __bound_ptr_indir8(void *p
, size_t offset
);
205 DLL_EXPORT
void * __bound_ptr_indir12(void *p
, size_t offset
);
206 DLL_EXPORT
void * __bound_ptr_indir16(void *p
, size_t offset
);
207 DLL_EXPORT
void FASTCALL
__bound_local_new(void *p1
);
208 DLL_EXPORT
void FASTCALL
__bound_local_delete(void *p1
);
209 void __bound_init(size_t *, int);
210 void __bound_main_arg(char **p
);
211 void __bound_exit(void);
213 void *__bound_mmap (void *start
, size_t size
, int prot
, int flags
, int fd
,
215 int __bound_munmap (void *start
, size_t size
);
216 DLL_EXPORT
void __bound_siglongjmp(jmp_buf env
, int val
);
218 DLL_EXPORT
void __bound_new_region(void *p
, size_t size
);
219 DLL_EXPORT
void __bound_setjmp(jmp_buf env
);
220 DLL_EXPORT
void __bound_longjmp(jmp_buf env
, int val
);
221 DLL_EXPORT
void *__bound_memcpy(void *dst
, const void *src
, size_t size
);
222 DLL_EXPORT
int __bound_memcmp(const void *s1
, const void *s2
, size_t size
);
223 DLL_EXPORT
void *__bound_memmove(void *dst
, const void *src
, size_t size
);
224 DLL_EXPORT
void *__bound_memset(void *dst
, int c
, size_t size
);
225 DLL_EXPORT
int __bound_strlen(const char *s
);
226 DLL_EXPORT
char *__bound_strcpy(char *dst
, const char *src
);
227 DLL_EXPORT
char *__bound_strncpy(char *dst
, const char *src
, size_t n
);
228 DLL_EXPORT
int __bound_strcmp(const char *s1
, const char *s2
);
229 DLL_EXPORT
int __bound_strncmp(const char *s1
, const char *s2
, size_t n
);
230 DLL_EXPORT
char *__bound_strcat(char *dest
, const char *src
);
231 DLL_EXPORT
char *__bound_strchr(const char *string
, int ch
);
232 DLL_EXPORT
char *__bound_strdup(const char *s
);
235 DLL_EXPORT
void *__bound___aeabi_memcpy(void *dst
, const void *src
, size_t size
);
236 DLL_EXPORT
void *__bound___aeabi_memmove(void *dst
, const void *src
, size_t size
);
237 DLL_EXPORT
void *__bound___aeabi_memmove4(void *dst
, const void *src
, size_t size
);
238 DLL_EXPORT
void *__bound___aeabi_memmove8(void *dst
, const void *src
, size_t size
);
239 DLL_EXPORT
void *__bound___aeabi_memset(void *dst
, int c
, size_t size
);
240 DLL_EXPORT
void *__aeabi_memcpy(void *dst
, const void *src
, size_t size
);
241 DLL_EXPORT
void *__aeabi_memmove(void *dst
, const void *src
, size_t size
);
242 DLL_EXPORT
void *__aeabi_memmove4(void *dst
, const void *src
, size_t size
);
243 DLL_EXPORT
void *__aeabi_memmove8(void *dst
, const void *src
, size_t size
);
244 DLL_EXPORT
void *__aeabi_memset(void *dst
, int c
, size_t size
);
248 #define BOUND_MALLOC(a) malloc_redir(a)
249 #define BOUND_MEMALIGN(a,b) memalign_redir(a,b)
250 #define BOUND_FREE(a) free_redir(a)
251 #define BOUND_REALLOC(a,b) realloc_redir(a,b)
252 #define BOUND_CALLOC(a,b) calloc_redir(a,b)
254 #define BOUND_MALLOC(a) malloc(a)
255 #define BOUND_MEMALIGN(a,b) memalign(a,b)
256 #define BOUND_FREE(a) free(a)
257 #define BOUND_REALLOC(a,b) realloc(a,b)
258 #define BOUND_CALLOC(a,b) calloc(a,b)
259 DLL_EXPORT
void *__bound_malloc(size_t size
, const void *caller
);
260 DLL_EXPORT
void *__bound_memalign(size_t size
, size_t align
, const void *caller
);
261 DLL_EXPORT
void __bound_free(void *ptr
, const void *caller
);
262 DLL_EXPORT
void *__bound_realloc(void *ptr
, size_t size
, const void *caller
);
263 DLL_EXPORT
void *__bound_calloc(size_t nmemb
, size_t size
);
266 #define FREE_REUSE_SIZE (100)
267 static unsigned int free_reuse_index
;
268 static void *free_reuse_list
[FREE_REUSE_SIZE
];
270 static Tree
*tree
= NULL
;
271 #define TREE_REUSE (1)
273 static Tree
*tree_free_list
;
275 static alloca_list_type
*alloca_list
;
276 static jmp_list_type
*jmp_list
;
278 static unsigned char inited
;
279 static unsigned char print_warn_ptr_add
;
280 static unsigned char print_calls
;
281 static unsigned char print_heap
;
282 static unsigned char print_statistic
;
283 static unsigned char no_strdup
;
284 static int never_fatal
;
285 static int no_checking
= 1;
286 static char exec
[100];
289 static unsigned long long bound_ptr_add_count
;
290 static unsigned long long bound_ptr_indir1_count
;
291 static unsigned long long bound_ptr_indir2_count
;
292 static unsigned long long bound_ptr_indir4_count
;
293 static unsigned long long bound_ptr_indir8_count
;
294 static unsigned long long bound_ptr_indir12_count
;
295 static unsigned long long bound_ptr_indir16_count
;
296 static unsigned long long bound_local_new_count
;
297 static unsigned long long bound_local_delete_count
;
298 static unsigned long long bound_malloc_count
;
299 static unsigned long long bound_calloc_count
;
300 static unsigned long long bound_realloc_count
;
301 static unsigned long long bound_free_count
;
302 static unsigned long long bound_memalign_count
;
303 static unsigned long long bound_mmap_count
;
304 static unsigned long long bound_munmap_count
;
305 static unsigned long long bound_alloca_count
;
306 static unsigned long long bound_setjmp_count
;
307 static unsigned long long bound_longjmp_count
;
308 static unsigned long long bound_mempcy_count
;
309 static unsigned long long bound_memcmp_count
;
310 static unsigned long long bound_memmove_count
;
311 static unsigned long long bound_memset_count
;
312 static unsigned long long bound_strlen_count
;
313 static unsigned long long bound_strcpy_count
;
314 static unsigned long long bound_strncpy_count
;
315 static unsigned long long bound_strcmp_count
;
316 static unsigned long long bound_strncmp_count
;
317 static unsigned long long bound_strcat_count
;
318 static unsigned long long bound_strchr_count
;
319 static unsigned long long bound_strdup_count
;
320 static unsigned long long bound_not_found
;
321 #define INCR_COUNT(x) ++x
323 #define INCR_COUNT(x)
325 #if BOUND_STATISTIC_SPLAY
326 static unsigned long long bound_splay
;
327 static unsigned long long bound_splay_end
;
328 static unsigned long long bound_splay_insert
;
329 static unsigned long long bound_splay_delete
;
330 #define INCR_COUNT_SPLAY(x) ++x
332 #define INCR_COUNT_SPLAY(x)
335 /* currently only i386/x86_64 supported. Change for other platforms */
336 static void fetch_and_add(int* variable
, int value
)
338 #if defined __i386__ || defined __x86_64__
339 __asm__
volatile("lock; addl %0, %1"
340 : "+r" (value
), "+m" (*variable
) // input+output
344 #elif defined __arm__
345 extern void fetch_and_add_arm(int* variable
, int value
);
346 fetch_and_add_arm(variable
, value
);
347 #elif defined __aarch64__
348 extern void fetch_and_add_arm64(int* variable
, int value
);
349 fetch_and_add_arm64(variable
, value
);
350 #elif defined __riscv
351 extern void fetch_and_add_riscv64(int* variable
, int value
);
352 fetch_and_add_riscv64(variable
, value
);
358 /* enable/disable checking. This can be used in signal handlers. */
359 void __bound_checking (int no_check
)
361 fetch_and_add (&no_checking
, no_check
);
364 /* enable/disable checking. This can be used in signal handlers. */
365 void __bound_never_fatal (int neverfatal
)
367 fetch_and_add (&never_fatal
, neverfatal
);
370 int tcc_backtrace(const char *fmt
, ...);
372 /* print a bound error message */
373 #define bound_warning(...) \
374 tcc_backtrace("^bcheck.c^BCHECK: " __VA_ARGS__)
376 #define bound_error(...) \
378 bound_warning(__VA_ARGS__); \
379 if (never_fatal == 0) \
383 static void bound_alloc_error(const char *s
)
385 fprintf(stderr
,"FATAL: %s\n",s
);
389 static void bound_not_found_warning(const char *file
, const char *function
,
392 dprintf(stderr
, "%s%s, %s(): Not found %p\n", exec
, file
, function
, ptr
);
395 /* return '(p + offset)' for pointer arithmetic (a pointer can reach
396 the end of a region in this case */
397 void * __bound_ptr_add(void *p
, size_t offset
)
399 size_t addr
= (size_t)p
;
404 dprintf(stderr
, "%s, %s(): %p 0x%lx\n",
405 __FILE__
, __FUNCTION__
, p
, (unsigned long)offset
);
408 INCR_COUNT(bound_ptr_add_count
);
411 if (addr
>= tree
->size
) {
413 tree
= splay (addr
, tree
);
416 if (addr
>= tree
->size
) {
418 tree
= splay_end (addr
, tree
);
421 if (addr
<= tree
->size
) {
422 if (tree
->is_invalid
|| addr
+ offset
> tree
->size
) {
424 if (print_warn_ptr_add
)
425 bound_warning("%p is outside of the region", p
+ offset
);
426 if (never_fatal
<= 0)
427 return INVALID_POINTER
; /* return an invalid pointer */
431 else if (p
) { /* Allow NULL + offset. offsetoff is using it. */
432 INCR_COUNT(bound_not_found
);
434 bound_not_found_warning (__FILE__
, __FUNCTION__
, p
);
442 /* return '(p + offset)' for pointer indirection (the resulting must
443 be strictly inside the region */
444 #define BOUND_PTR_INDIR(dsize) \
445 void * __bound_ptr_indir ## dsize (void *p, size_t offset) \
447 size_t addr = (size_t)p; \
452 dprintf(stderr, "%s, %s(): %p 0x%lx\n", \
453 __FILE__, __FUNCTION__, p, (unsigned long)offset); \
455 INCR_COUNT(bound_ptr_indir ## dsize ## _count); \
457 addr -= tree->start; \
458 if (addr >= tree->size) { \
460 tree = splay (addr, tree); \
461 addr -= tree->start; \
463 if (addr >= tree->size) { \
465 tree = splay_end (addr, tree); \
466 addr -= tree->start; \
468 if (addr <= tree->size) { \
469 if (tree->is_invalid || addr + offset + dsize > tree->size) { \
471 bound_warning("%p is outside of the region", p + offset); \
472 if (never_fatal <= 0) \
473 return INVALID_POINTER; /* return an invalid pointer */ \
478 INCR_COUNT(bound_not_found); \
480 bound_not_found_warning (__FILE__, __FUNCTION__, p); \
495 #if defined(__GNUC__) && (__GNUC__ >= 6)
497 * At least gcc 6.2 complains when __builtin_frame_address is used with
500 #pragma GCC diagnostic push
501 #pragma GCC diagnostic ignored "-Wframe-address"
504 /* return the frame pointer of the caller */
505 #define GET_CALLER_FP(fp)\
507 fp = (size_t)__builtin_frame_address(1);\
510 /* called when entering a function to add all the local regions */
511 void FASTCALL
__bound_local_new(void *p1
)
513 size_t addr
, fp
, *p
= p1
;
518 dprintf(stderr
, "%s, %s(): p1=%p fp=%p\n",
519 __FILE__
, __FUNCTION__
, p
, (void *)fp
);
521 while ((addr
= p
[0])) {
522 INCR_COUNT(bound_local_new_count
);
523 tree
= splay_insert(addr
+ fp
, p
[1], tree
);
530 while ((addr
= p
[0])) {
531 dprintf(stderr
, "%s, %s(): %p 0x%lx\n",
532 __FILE__
, __FUNCTION__
,
533 (void *) (addr
+ fp
), (unsigned long) p
[1]);
540 /* called when leaving a function to delete all the local regions */
541 void FASTCALL
__bound_local_delete(void *p1
)
543 size_t addr
, fp
, *p
= p1
;
548 dprintf(stderr
, "%s, %s(): p1=%p fp=%p\n",
549 __FILE__
, __FUNCTION__
, p
, (void *)fp
);
551 while ((addr
= p
[0])) {
552 INCR_COUNT(bound_local_delete_count
);
553 tree
= splay_delete(addr
+ fp
, tree
);
557 alloca_list_type
*last
= NULL
;
558 alloca_list_type
*cur
= alloca_list
;
563 last
->next
= cur
->next
;
565 alloca_list
= cur
->next
;
566 tree
= splay_delete ((size_t) cur
->p
, tree
);
567 dprintf(stderr
, "%s, %s(): remove alloca/vla %p\n",
568 __FILE__
, __FUNCTION__
, cur
->p
);
570 cur
= last
? last
->next
: alloca_list
;
579 jmp_list_type
*last
= NULL
;
580 jmp_list_type
*cur
= jmp_list
;
585 last
->next
= cur
->next
;
587 jmp_list
= cur
->next
;
588 dprintf(stderr
, "%s, %s(): remove setjmp %p\n",
589 __FILE__
, __FUNCTION__
, cur
->penv
);
591 cur
= last
? last
->next
: jmp_list
;
604 while ((addr
= p
[0])) {
606 dprintf(stderr
, "%s, %s(): %p 0x%lx\n",
607 __FILE__
, __FUNCTION__
,
608 (void *) (addr
+ fp
), (unsigned long) p
[1]);
617 void __bound_new_region(void *p
, size_t size
)
620 alloca_list_type
*last
;
621 alloca_list_type
*cur
;
622 alloca_list_type
*new;
624 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
625 __FILE__
, __FUNCTION__
, p
, (unsigned long)size
);
627 new = BOUND_MALLOC (sizeof (alloca_list_type
));
629 INCR_COUNT(bound_alloca_count
);
633 if (cur
->fp
== fp
&& cur
->p
== p
) {
635 last
->next
= cur
->next
;
637 alloca_list
= cur
->next
;
638 tree
= splay_delete((size_t)p
, tree
);
644 if (no_checking
== 0)
645 tree
= splay_insert((size_t)p
, size
, tree
);
649 new->next
= alloca_list
;
654 dprintf(stderr
, "%s, %s(): remove alloca/vla %p\n",
655 __FILE__
, __FUNCTION__
, cur
->p
);
660 void __bound_setjmp(jmp_buf env
)
663 void *e
= (void *) env
;
665 if (no_checking
== 0) {
666 dprintf(stderr
, "%s, %s(): %p\n", __FILE__
, __FUNCTION__
, e
);
668 INCR_COUNT(bound_setjmp_count
);
676 jl
= BOUND_MALLOC (sizeof (jmp_list_type
));
688 jl
->end_fp
= (size_t)__builtin_frame_address(0);
689 jl
->tid
= BOUND_GET_TID
;
695 static void __bound_long_jump(jmp_buf env
, int val
, int sig
, const char *func
)
701 if (no_checking
== 0) {
704 dprintf(stderr
, "%s, %s(): %p\n", __FILE__
, func
, e
);
706 INCR_COUNT(bound_longjmp_count
);
709 if (jl
->penv
== e
&& jl
->tid
== tid
) {
710 size_t start_fp
= (size_t)__builtin_frame_address(0);
711 size_t end_fp
= jl
->end_fp
;
712 jmp_list_type
*cur
= jmp_list
;
713 jmp_list_type
*last
= NULL
;
715 while (cur
->penv
!= e
|| cur
->tid
!= tid
) {
716 if (cur
->tid
== tid
) {
717 dprintf(stderr
, "%s, %s(): remove setjmp %p\n",
718 __FILE__
, func
, cur
->penv
);
720 last
->next
= cur
->next
;
722 jmp_list
= cur
->next
;
724 cur
= last
? last
->next
: jmp_list
;
733 alloca_list_type
*last
;
734 alloca_list_type
*cur
;
736 while (t
&& (t
->start
< start_fp
|| t
->start
> end_fp
))
737 if (t
->start
< start_fp
)
746 if ((size_t) cur
->p
== t
->start
) {
747 dprintf(stderr
, "%s, %s(): remove alloca/vla %p\n",
748 __FILE__
, func
, cur
->p
);
750 last
->next
= cur
->next
;
752 alloca_list
= cur
->next
;
759 dprintf(stderr
, "%s, %s(): delete %p\n",
760 __FILE__
, func
, (void *) t
->start
);
761 tree
= splay_delete(t
->start
, tree
);
770 sig
? siglongjmp(env
, val
) :
775 void __bound_longjmp(jmp_buf env
, int val
)
777 __bound_long_jump(env
,val
, 0, __FUNCTION__
);
781 void __bound_siglongjmp(jmp_buf env
, int val
)
783 __bound_long_jump(env
,val
, 1, __FUNCTION__
);
787 #if defined(__GNUC__) && (__GNUC__ >= 6)
788 #pragma GCC diagnostic pop
791 void __bound_init(size_t *p
, int mode
)
793 dprintf(stderr
, "%s, %s(): start %s\n", __FILE__
, __FUNCTION__
,
794 mode
< 0 ? "lazy" : mode
== 0 ? "normal use" : "for -run");
802 print_warn_ptr_add
= getenv ("TCC_BOUNDS_WARN_POINTER_ADD") != NULL
;
803 print_calls
= getenv ("TCC_BOUNDS_PRINT_CALLS") != NULL
;
804 print_heap
= getenv ("TCC_BOUNDS_PRINT_HEAP") != NULL
;
805 print_statistic
= getenv ("TCC_BOUNDS_PRINT_STATISTIC") != NULL
;
806 never_fatal
= getenv ("TCC_BOUNDS_NEVER_FATAL") != NULL
;
812 void *addr
= mode
> 0 ? RTLD_DEFAULT
: RTLD_NEXT
;
814 /* tcc -run required RTLD_DEFAULT. Normal usage requires RTLD_NEXT,
815 but using RTLD_NEXT with -run segfaults on MacOS in dyld as the
816 generated code segment isn't registered with dyld and hence the
817 caller image of dlsym isn't known to it */
818 *(void **) (&malloc_redir
) = dlsym (addr
, "malloc");
819 if (malloc_redir
== NULL
) {
820 dprintf(stderr
, "%s, %s(): use RTLD_DEFAULT\n",
821 __FILE__
, __FUNCTION__
);
823 *(void **) (&malloc_redir
) = dlsym (addr
, "malloc");
825 *(void **) (&calloc_redir
) = dlsym (addr
, "calloc");
826 *(void **) (&free_redir
) = dlsym (addr
, "free");
827 *(void **) (&realloc_redir
) = dlsym (addr
, "realloc");
828 *(void **) (&memalign_redir
) = dlsym (addr
, "memalign");
829 dprintf(stderr
, "%s, %s(): malloc_redir %p\n",
830 __FILE__
, __FUNCTION__
, malloc_redir
);
831 dprintf(stderr
, "%s, %s(): free_redir %p\n",
832 __FILE__
, __FUNCTION__
, free_redir
);
833 dprintf(stderr
, "%s, %s(): realloc_redir %p\n",
834 __FILE__
, __FUNCTION__
, realloc_redir
);
835 dprintf(stderr
, "%s, %s(): memalign_redir %p\n",
836 __FILE__
, __FUNCTION__
, memalign_redir
);
837 if (malloc_redir
== NULL
|| free_redir
== NULL
)
838 bound_alloc_error ("Cannot redirect malloc/free");
839 #if HAVE_PTHREAD_CREATE
840 *(void **) (&pthread_create_redir
) = dlsym (addr
, "pthread_create");
841 dprintf(stderr
, "%s, %s(): pthread_create_redir %p\n",
842 __FILE__
, __FUNCTION__
, pthread_create_redir
);
854 (unsigned long) __builtin_return_address(0);
857 /* Display exec name. Usefull when a lot of code is compiled with tcc */
858 fp
= fopen ("/proc/self/comm", "r");
860 memset (exec
, 0, sizeof(exec
));
861 fread (exec
, 1, sizeof(exec
) - 2, fp
);
862 if (strchr(exec
,'\n'))
863 *strchr(exec
,'\n') = '\0';
867 /* check if dlopen is used (is threre a better way?) */
869 fp
= fopen ("/proc/self/maps", "r");
871 while (fgets (line
, sizeof(line
), fp
)) {
872 if (sscanf (line
, "%lx-%lx", &start
, &end
) == 2 &&
873 ad
>= start
&& ad
< end
) {
877 if (strstr (line
,"[heap]"))
893 #warning fill out for MacOS (see <_ctype.h> and <runetype.h>)
895 /* XXX: Does not work if locale is changed */
896 tree
= splay_insert((size_t) __ctype_b_loc(),
897 sizeof (unsigned short *), tree
);
898 tree
= splay_insert((size_t) (*__ctype_b_loc() - 128),
899 384 * sizeof (unsigned short), tree
);
900 tree
= splay_insert((size_t) __ctype_tolower_loc(),
901 sizeof (__int32_t
*), tree
);
902 tree
= splay_insert((size_t) (*__ctype_tolower_loc() - 128),
903 384 * sizeof (__int32_t
), tree
);
904 tree
= splay_insert((size_t) __ctype_toupper_loc(),
905 sizeof (__int32_t
*), tree
);
906 tree
= splay_insert((size_t) (*__ctype_toupper_loc() - 128),
907 384 * sizeof (__int32_t
), tree
);
911 tree
= splay_insert((size_t) (&errno
), sizeof (int), tree
);
918 /* add all static bound check values */
920 tree
= splay_insert(p
[0], p
[1], tree
);
923 dprintf(stderr
, "%s, %s(): static var %p 0x%lx\n",
924 __FILE__
, __FUNCTION__
,
925 (void *) p
[0], (unsigned long) p
[1]);
934 dprintf(stderr
, "%s, %s(): end\n\n", __FILE__
, __FUNCTION__
);
937 void __bound_main_arg(char **p
)
939 char *start
= (char *) p
;
943 tree
= splay_insert((size_t) *p
, strlen (*p
) + 1, tree
);
946 tree
= splay_insert((size_t) start
, (char *) p
- start
, tree
);
952 dprintf(stderr
, "%s, %s(): %p 0x%lx\n",
953 __FILE__
, __FUNCTION__
,
954 *p
, (unsigned long)(strlen (*p
) + 1));
957 dprintf(stderr
, "%s, %s(): argv %p 0x%lx\n",
958 __FILE__
, __FUNCTION__
,
959 start
, (unsigned long)((char *) p
- start
));
965 extern char **environ
;
971 tree
= splay_insert((size_t) *p
, strlen (*p
) + 1, tree
);
974 tree
= splay_insert((size_t) start
, (char *) p
- start
, tree
);
980 dprintf(stderr
, "%s, %s(): %p 0x%lx\n",
981 __FILE__
, __FUNCTION__
,
982 *p
, (unsigned long)(strlen (*p
) + 1));
985 dprintf(stderr
, "%s, %s(): environ %p 0x%lx\n",
986 __FILE__
, __FUNCTION__
,
987 start
, (unsigned long)((char *) p
- start
));
994 void __attribute__((destructor
)) __bound_exit(void)
997 static const char * const alloc_type
[] = {
998 "", "malloc", "calloc", "realloc", "memalign", "strdup"
1001 dprintf(stderr
, "%s, %s():\n", __FILE__
, __FUNCTION__
);
1004 #if !defined(_WIN32) && !defined(__APPLE__)
1006 extern void __libc_freeres (void);
1014 while (alloca_list
) {
1015 alloca_list_type
*next
= alloca_list
->next
;
1017 tree
= splay_delete ((size_t) alloca_list
->p
, tree
);
1018 BOUND_FREE (alloca_list
);
1022 jmp_list_type
*next
= jmp_list
->next
;
1024 BOUND_FREE (jmp_list
);
1027 for (i
= 0; i
< FREE_REUSE_SIZE
; i
++) {
1028 if (free_reuse_list
[i
]) {
1029 tree
= splay_delete ((size_t) free_reuse_list
[i
], tree
);
1030 BOUND_FREE (free_reuse_list
[i
]);
1034 if (print_heap
&& tree
->type
!= 0)
1035 fprintf (stderr
, "%s, %s(): %s found size %lu\n",
1036 __FILE__
, __FUNCTION__
, alloc_type
[tree
->type
],
1037 (unsigned long) tree
->size
);
1038 tree
= splay_delete (tree
->start
, tree
);
1041 while (tree_free_list
) {
1042 Tree
*next
= tree_free_list
->left
;
1043 BOUND_FREE (tree_free_list
);
1044 tree_free_list
= next
;
1050 if (print_statistic
) {
1052 fprintf (stderr
, "bound_ptr_add_count %llu\n", bound_ptr_add_count
);
1053 fprintf (stderr
, "bound_ptr_indir1_count %llu\n", bound_ptr_indir1_count
);
1054 fprintf (stderr
, "bound_ptr_indir2_count %llu\n", bound_ptr_indir2_count
);
1055 fprintf (stderr
, "bound_ptr_indir4_count %llu\n", bound_ptr_indir4_count
);
1056 fprintf (stderr
, "bound_ptr_indir8_count %llu\n", bound_ptr_indir8_count
);
1057 fprintf (stderr
, "bound_ptr_indir12_count %llu\n", bound_ptr_indir12_count
);
1058 fprintf (stderr
, "bound_ptr_indir16_count %llu\n", bound_ptr_indir16_count
);
1059 fprintf (stderr
, "bound_local_new_count %llu\n", bound_local_new_count
);
1060 fprintf (stderr
, "bound_local_delete_count %llu\n", bound_local_delete_count
);
1061 fprintf (stderr
, "bound_malloc_count %llu\n", bound_malloc_count
);
1062 fprintf (stderr
, "bound_calloc_count %llu\n", bound_calloc_count
);
1063 fprintf (stderr
, "bound_realloc_count %llu\n", bound_realloc_count
);
1064 fprintf (stderr
, "bound_free_count %llu\n", bound_free_count
);
1065 fprintf (stderr
, "bound_memalign_count %llu\n", bound_memalign_count
);
1066 fprintf (stderr
, "bound_mmap_count %llu\n", bound_mmap_count
);
1067 fprintf (stderr
, "bound_munmap_count %llu\n", bound_munmap_count
);
1068 fprintf (stderr
, "bound_alloca_count %llu\n", bound_alloca_count
);
1069 fprintf (stderr
, "bound_setjmp_count %llu\n", bound_setjmp_count
);
1070 fprintf (stderr
, "bound_longjmp_count %llu\n", bound_longjmp_count
);
1071 fprintf (stderr
, "bound_mempcy_count %llu\n", bound_mempcy_count
);
1072 fprintf (stderr
, "bound_memcmp_count %llu\n", bound_memcmp_count
);
1073 fprintf (stderr
, "bound_memmove_count %llu\n", bound_memmove_count
);
1074 fprintf (stderr
, "bound_memset_count %llu\n", bound_memset_count
);
1075 fprintf (stderr
, "bound_strlen_count %llu\n", bound_strlen_count
);
1076 fprintf (stderr
, "bound_strcpy_count %llu\n", bound_strcpy_count
);
1077 fprintf (stderr
, "bound_strncpy_count %llu\n", bound_strncpy_count
);
1078 fprintf (stderr
, "bound_strcmp_count %llu\n", bound_strcmp_count
);
1079 fprintf (stderr
, "bound_strncmp_count %llu\n", bound_strncmp_count
);
1080 fprintf (stderr
, "bound_strcat_count %llu\n", bound_strcat_count
);
1081 fprintf (stderr
, "bound_strchr_count %llu\n", bound_strchr_count
);
1082 fprintf (stderr
, "bound_strdup_count %llu\n", bound_strdup_count
);
1083 fprintf (stderr
, "bound_not_found %llu\n", bound_not_found
);
1085 #if BOUND_STATISTIC_SPLAY
1086 fprintf (stderr
, "bound_splay %llu\n", bound_splay
);
1087 fprintf (stderr
, "bound_splay_end %llu\n", bound_splay_end
);
1088 fprintf (stderr
, "bound_splay_insert %llu\n", bound_splay_insert
);
1089 fprintf (stderr
, "bound_splay_delete %llu\n", bound_splay_delete
);
1095 #if HAVE_PTHREAD_CREATE
1096 int pthread_create(pthread_t
*thread
, const pthread_attr_t
*attr
,
1097 void *(*start_routine
) (void *), void *arg
)
1100 dprintf (stderr
, "%s, %s()\n", __FILE__
, __FUNCTION__
);
1101 return pthread_create_redir(thread
, attr
, start_routine
, arg
);
1106 void *malloc(size_t size
)
1108 void *__bound_malloc(size_t size
, const void *caller
)
1114 /* This will catch the first dlsym call from __bound_init */
1115 if (malloc_redir
== NULL
) {
1116 __bound_init (0, -1);
1117 if (malloc_redir
== NULL
) {
1118 ptr
= &initial_pool
[pool_index
];
1119 pool_index
= (pool_index
+ size
+ 15) & ~15;
1120 if (pool_index
>= sizeof (initial_pool
))
1121 bound_alloc_error ("initial memory pool too small");
1122 dprintf (stderr
, "%s, %s(): initial %p, 0x%lx\n",
1123 __FILE__
, __FUNCTION__
, ptr
, (unsigned long)size
);
1128 /* we allocate one more byte to ensure the regions will be
1129 separated by at least one byte. With the glibc malloc, it may
1130 be in fact not necessary */
1131 ptr
= BOUND_MALLOC (size
+ 1);
1132 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1133 __FILE__
, __FUNCTION__
, ptr
, (unsigned long)size
);
1135 if (no_checking
== 0) {
1137 INCR_COUNT(bound_malloc_count
);
1140 tree
= splay_insert ((size_t) ptr
, size
? size
: size
+ 1, tree
);
1141 if (tree
&& tree
->start
== (size_t) ptr
)
1142 tree
->type
= TCC_TYPE_MALLOC
;
1150 void *memalign(size_t size
, size_t align
)
1152 void *__bound_memalign(size_t size
, size_t align
, const void *caller
)
1158 /* we allocate one more byte to ensure the regions will be
1159 separated by at least one byte. With the glibc malloc, it may
1160 be in fact not necessary */
1161 ptr
= BOUND_MEMALIGN(size
+ 1, align
);
1164 /* XXX: handle it ? */
1167 /* we suppose that malloc aligns to at least four bytes */
1168 ptr
= BOUND_MALLOC(size
+ 1);
1171 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1172 __FILE__
, __FUNCTION__
, ptr
, (unsigned long)size
);
1174 if (no_checking
== 0) {
1176 INCR_COUNT(bound_memalign_count
);
1179 tree
= splay_insert((size_t) ptr
, size
? size
: size
+ 1, tree
);
1180 if (tree
&& tree
->start
== (size_t) ptr
)
1181 tree
->type
= TCC_TYPE_MEMALIGN
;
1189 void free(void *ptr
)
1191 void __bound_free(void *ptr
, const void *caller
)
1194 size_t addr
= (size_t) ptr
;
1197 if (ptr
== NULL
|| tree
== NULL
|| no_checking
1199 || ((unsigned char *) ptr
>= &initial_pool
[0] &&
1200 (unsigned char *) ptr
< &initial_pool
[sizeof(initial_pool
)])
1205 dprintf(stderr
, "%s, %s(): %p\n", __FILE__
, __FUNCTION__
, ptr
);
1208 INCR_COUNT(bound_free_count
);
1209 tree
= splay (addr
, tree
);
1210 if (tree
->start
== addr
) {
1211 if (tree
->is_invalid
) {
1213 bound_error("freeing invalid region");
1216 tree
->is_invalid
= 1;
1217 memset (ptr
, 0x5a, tree
->size
);
1218 p
= free_reuse_list
[free_reuse_index
];
1219 free_reuse_list
[free_reuse_index
] = ptr
;
1220 free_reuse_index
= (free_reuse_index
+ 1) % FREE_REUSE_SIZE
;
1222 tree
= splay_delete((size_t)p
, tree
);
1230 void *realloc(void *ptr
, size_t size
)
1232 void *__bound_realloc(void *ptr
, size_t size
, const void *caller
)
1241 __bound_free(ptr
, caller
);
1246 new_ptr
= BOUND_REALLOC (ptr
, size
+ 1);
1247 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1248 __FILE__
, __FUNCTION__
, new_ptr
, (unsigned long)size
);
1250 if (no_checking
== 0) {
1252 INCR_COUNT(bound_realloc_count
);
1255 tree
= splay_delete ((size_t) ptr
, tree
);
1257 tree
= splay_insert ((size_t) new_ptr
, size
? size
: size
+ 1, tree
);
1258 if (tree
&& tree
->start
== (size_t) new_ptr
)
1259 tree
->type
= TCC_TYPE_REALLOC
;
1267 void *calloc(size_t nmemb
, size_t size
)
1269 void *__bound_calloc(size_t nmemb
, size_t size
)
1276 /* This will catch the first dlsym call from __bound_init */
1277 if (malloc_redir
== NULL
) {
1278 __bound_init (0, -1);
1279 if (malloc_redir
== NULL
) {
1280 ptr
= &initial_pool
[pool_index
];
1281 pool_index
= (pool_index
+ size
+ 15) & ~15;
1282 if (pool_index
>= sizeof (initial_pool
))
1283 bound_alloc_error ("initial memory pool too small");
1284 dprintf (stderr
, "%s, %s(): initial %p, 0x%lx\n",
1285 __FILE__
, __FUNCTION__
, ptr
, (unsigned long)size
);
1286 memset (ptr
, 0, size
);
1291 ptr
= BOUND_MALLOC(size
+ 1);
1292 dprintf (stderr
, "%s, %s(): %p, 0x%lx\n",
1293 __FILE__
, __FUNCTION__
, ptr
, (unsigned long)size
);
1296 memset (ptr
, 0, size
);
1297 if (no_checking
== 0) {
1299 INCR_COUNT(bound_calloc_count
);
1300 tree
= splay_insert ((size_t) ptr
, size
? size
: size
+ 1, tree
);
1301 if (tree
&& tree
->start
== (size_t) ptr
)
1302 tree
->type
= TCC_TYPE_CALLOC
;
1309 #if !defined(_WIN32)
1310 void *__bound_mmap (void *start
, size_t size
, int prot
,
1311 int flags
, int fd
, off_t offset
)
1315 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1316 __FILE__
, __FUNCTION__
, start
, (unsigned long)size
);
1317 result
= mmap (start
, size
, prot
, flags
, fd
, offset
);
1318 if (result
&& no_checking
== 0) {
1320 INCR_COUNT(bound_mmap_count
);
1321 tree
= splay_insert((size_t)result
, size
, tree
);
1327 int __bound_munmap (void *start
, size_t size
)
1331 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1332 __FILE__
, __FUNCTION__
, start
, (unsigned long)size
);
1333 if (start
&& no_checking
== 0) {
1335 INCR_COUNT(bound_munmap_count
);
1336 tree
= splay_delete ((size_t) start
, tree
);
1339 result
= munmap (start
, size
);
1344 /* some useful checked functions */
1346 /* check that (p ... p + size - 1) lies inside 'p' region, if any */
1347 static void __bound_check(const void *p
, size_t size
, const char *function
)
1349 if (no_checking
== 0 && size
!= 0 &&
1350 __bound_ptr_add((void *)p
, size
) == INVALID_POINTER
) {
1351 bound_error("invalid pointer %p, size 0x%lx in %s",
1352 p
, (unsigned long)size
, function
);
1356 static int check_overlap (const void *p1
, size_t n1
,
1357 const void *p2
, size_t n2
,
1358 const char *function
)
1360 const void *p1e
= (const void *) ((const char *) p1
+ n1
);
1361 const void *p2e
= (const void *) ((const char *) p2
+ n2
);
1363 if (no_checking
== 0 && n1
!= 0 && n2
!=0 &&
1364 ((p1
<= p2
&& p1e
> p2
) || /* p1----p2====p1e----p2e */
1365 (p2
<= p1
&& p2e
> p1
))) { /* p2----p1====p2e----p1e */
1366 bound_error("overlapping regions %p(0x%lx), %p(0x%lx) in %s",
1367 p1
, (unsigned long)n1
, p2
, (unsigned long)n2
, function
);
1368 return never_fatal
< 0;
1373 void *__bound_memcpy(void *dest
, const void *src
, size_t n
)
1375 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1376 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1377 INCR_COUNT(bound_mempcy_count
);
1378 __bound_check(dest
, n
, "memcpy dest");
1379 __bound_check(src
, n
, "memcpy src");
1380 if (check_overlap(dest
, n
, src
, n
, "memcpy"))
1382 return memcpy(dest
, src
, n
);
1385 int __bound_memcmp(const void *s1
, const void *s2
, size_t n
)
1387 const unsigned char *u1
= (const unsigned char *) s1
;
1388 const unsigned char *u2
= (const unsigned char *) s2
;
1391 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1392 __FILE__
, __FUNCTION__
, s1
, s2
, (unsigned long)n
);
1393 INCR_COUNT(bound_memcmp_count
);
1395 if ((ssize_t
) --n
== -1)
1397 else if (*u1
!= *u2
) {
1398 retval
= *u1
++ - *u2
++;
1404 __bound_check(s1
, (const void *)u1
- s1
, "memcmp s1");
1405 __bound_check(s2
, (const void *)u2
- s2
, "memcmp s2");
1409 void *__bound_memmove(void *dest
, const void *src
, size_t n
)
1411 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1412 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1413 INCR_COUNT(bound_memmove_count
);
1414 __bound_check(dest
, n
, "memmove dest");
1415 __bound_check(src
, n
, "memmove src");
1416 return memmove(dest
, src
, n
);
1419 void *__bound_memset(void *s
, int c
, size_t n
)
1421 dprintf(stderr
, "%s, %s(): %p, %d, 0x%lx\n",
1422 __FILE__
, __FUNCTION__
, s
, c
, (unsigned long)n
);
1423 INCR_COUNT(bound_memset_count
);
1424 __bound_check(s
, n
, "memset");
1425 return memset(s
, c
, n
);
1428 #if defined(__arm__)
1429 void *__bound___aeabi_memcpy(void *dest
, const void *src
, size_t n
)
1431 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1432 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1433 INCR_COUNT(bound_mempcy_count
);
1434 __bound_check(dest
, n
, "memcpy dest");
1435 __bound_check(src
, n
, "memcpy src");
1436 if (check_overlap(dest
, n
, src
, n
, "memcpy"))
1438 return __aeabi_memcpy(dest
, src
, n
);
1441 void *__bound___aeabi_memmove(void *dest
, const void *src
, size_t n
)
1443 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1444 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1445 INCR_COUNT(bound_memmove_count
);
1446 __bound_check(dest
, n
, "memmove dest");
1447 __bound_check(src
, n
, "memmove src");
1448 return __aeabi_memmove(dest
, src
, n
);
1451 void *__bound___aeabi_memmove4(void *dest
, const void *src
, size_t n
)
1453 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1454 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1455 INCR_COUNT(bound_memmove_count
);
1456 __bound_check(dest
, n
, "memmove dest");
1457 __bound_check(src
, n
, "memmove src");
1458 return __aeabi_memmove4(dest
, src
, n
);
1461 void *__bound___aeabi_memmove8(void *dest
, const void *src
, size_t n
)
1463 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1464 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1465 INCR_COUNT(bound_memmove_count
);
1466 __bound_check(dest
, n
, "memmove dest");
1467 __bound_check(src
, n
, "memmove src");
1468 return __aeabi_memmove8(dest
, src
, n
);
1471 void *__bound___aeabi_memset(void *s
, int c
, size_t n
)
1473 dprintf(stderr
, "%s, %s(): %p, %d, 0x%lx\n",
1474 __FILE__
, __FUNCTION__
, s
, c
, (unsigned long)n
);
1475 INCR_COUNT(bound_memset_count
);
1476 __bound_check(s
, n
, "memset");
1477 return __aeabi_memset(s
, c
, n
);
1481 int __bound_strlen(const char *s
)
1485 dprintf(stderr
, "%s, %s(): %p\n",
1486 __FILE__
, __FUNCTION__
, s
);
1487 INCR_COUNT(bound_strlen_count
);
1489 __bound_check(s
, p
- s
, "strlen");
1493 char *__bound_strcpy(char *dest
, const char *src
)
1496 const char *p
= src
;
1498 dprintf(stderr
, "%s, %s(): %p, %p\n",
1499 __FILE__
, __FUNCTION__
, dest
, src
);
1500 INCR_COUNT(bound_strcpy_count
);
1503 __bound_check(dest
, len
, "strcpy dest");
1504 __bound_check(src
, len
, "strcpy src");
1505 if (check_overlap(dest
, len
, src
, len
, "strcpy"))
1507 return strcpy (dest
, src
);
1510 char *__bound_strncpy(char *dest
, const char *src
, size_t n
)
1513 const char *p
= src
;
1515 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1516 __FILE__
, __FUNCTION__
, dest
, src
, (unsigned long)n
);
1517 INCR_COUNT(bound_strncpy_count
);
1518 while (len
-- && *p
++);
1520 __bound_check(dest
, len
, "strncpy dest");
1521 __bound_check(src
, len
, "strncpy src");
1522 if (check_overlap(dest
, len
, src
, len
, "strncpy"))
1524 return strncpy(dest
, src
, n
);
1527 int __bound_strcmp(const char *s1
, const char *s2
)
1529 const unsigned char *u1
= (const unsigned char *) s1
;
1530 const unsigned char *u2
= (const unsigned char *) s2
;
1532 dprintf(stderr
, "%s, %s(): %p, %p\n",
1533 __FILE__
, __FUNCTION__
, s1
, s2
);
1534 INCR_COUNT(bound_strcmp_count
);
1535 while (*u1
&& *u1
== *u2
) {
1539 __bound_check(s1
, ((const char *)u1
- s1
) + 1, "strcmp s1");
1540 __bound_check(s2
, ((const char *)u2
- s2
) + 1, "strcmp s2");
1544 int __bound_strncmp(const char *s1
, const char *s2
, size_t n
)
1546 const unsigned char *u1
= (const unsigned char *) s1
;
1547 const unsigned char *u2
= (const unsigned char *) s2
;
1550 dprintf(stderr
, "%s, %s(): %p, %p, 0x%lx\n",
1551 __FILE__
, __FUNCTION__
, s1
, s2
, (unsigned long)n
);
1552 INCR_COUNT(bound_strncmp_count
);
1554 if ((ssize_t
) --n
== -1)
1556 else if (*u1
!= *u2
) {
1557 retval
= *u1
++ - *u2
++;
1562 __bound_check(s1
, (const char *)u1
- s1
, "strncmp s1");
1563 __bound_check(s2
, (const char *)u2
- s2
, "strncmp s2");
1567 char *__bound_strcat(char *dest
, const char *src
)
1570 const char *s
= src
;
1572 dprintf(stderr
, "%s, %s(): %p, %p\n",
1573 __FILE__
, __FUNCTION__
, dest
, src
);
1574 INCR_COUNT(bound_strcat_count
);
1577 __bound_check(r
, (dest
- r
) + (src
- s
) - 1, "strcat dest");
1578 __bound_check(s
, src
- s
, "strcat src");
1579 if (check_overlap(r
, (dest
- r
) + (src
- s
) - 1, s
, src
- s
, "strcat"))
1581 return strcat(r
, s
);
1584 char *__bound_strchr(const char *s
, int c
)
1586 const unsigned char *str
= (const unsigned char *) s
;
1587 unsigned char ch
= c
;
1589 dprintf(stderr
, "%s, %s(): %p, %d\n",
1590 __FILE__
, __FUNCTION__
, s
, ch
);
1591 INCR_COUNT(bound_strchr_count
);
1597 __bound_check(s
, ((const char *)str
- s
) + 1, "strchr");
1598 return *str
== ch
? (char *) str
: NULL
;
1601 char *__bound_strdup(const char *s
)
1606 INCR_COUNT(bound_strdup_count
);
1608 __bound_check(s
, p
- s
, "strdup");
1609 new = BOUND_MALLOC ((p
- s
) + 1);
1610 dprintf(stderr
, "%s, %s(): %p, 0x%lx\n",
1611 __FILE__
, __FUNCTION__
, new, (unsigned long)(p
-s
));
1613 if (no_checking
== 0 && no_strdup
== 0) {
1615 tree
= splay_insert((size_t)new, p
- s
, tree
);
1616 if (tree
&& tree
->start
== (size_t) new)
1617 tree
->type
= TCC_TYPE_STRDUP
;
1620 memcpy (new, s
, p
- s
);
1626 An implementation of top-down splaying with sizes
1627 D. Sleator <sleator@cs.cmu.edu>, January 1994.
1629 This extends top-down-splay.c to maintain a size field in each node.
1630 This is the number of nodes in the subtree rooted there. This makes
1631 it possible to efficiently compute the rank of a key. (The rank is
1632 the number of nodes to the left of the given key.) It it also
1633 possible to quickly find the node of a given rank. Both of these
1634 operations are illustrated in the code below. The remainder of this
1635 introduction is taken from top-down-splay.c.
1637 "Splay trees", or "self-adjusting search trees" are a simple and
1638 efficient data structure for storing an ordered set. The data
1639 structure consists of a binary tree, with no additional fields. It
1640 allows searching, insertion, deletion, deletemin, deletemax,
1641 splitting, joining, and many other operations, all with amortized
1642 logarithmic performance. Since the trees adapt to the sequence of
1643 requests, their performance on real access patterns is typically even
1644 better. Splay trees are described in a number of texts and papers
1647 The code here is adapted from simple top-down splay, at the bottom of
1648 page 669 of [2]. It can be obtained via anonymous ftp from
1649 spade.pc.cs.cmu.edu in directory /usr/sleator/public.
1651 The chief modification here is that the splay operation works even if the
1652 item being splayed is not in the tree, and even if the tree root of the
1653 tree is NULL. So the line:
1657 causes it to search for item with key i in the tree rooted at t. If it's
1658 there, it is splayed to the root. If it isn't there, then the node put
1659 at the root is the last one before NULL that would have been reached in a
1660 normal binary search for i. (It's a neighbor of i in the tree.) This
1661 allows many other operations to be easily implemented, as shown below.
1663 [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
1664 Harper Collins, 1991, pp 243-251.
1665 [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
1666 JACM Volume 32, No 3, July 1985, pp 652-686.
1667 [3] "Data Structure and Algorithm Analysis", Mark Weiss,
1668 Benjamin Cummins, 1992, pp 119-130.
1669 [4] "Data Structures, Algorithms, and Performance", Derick Wood,
1670 Addison-Wesley, 1993, pp 367-375
1673 /* Code adapted for tcc */
1675 #define compare(start,tstart,tsize) (start < tstart ? -1 : \
1676 start >= tstart+tsize ? 1 : 0)
1678 static Tree
* splay (size_t addr
, Tree
*t
)
1679 /* Splay using the key start (which may or may not be in the tree.) */
1680 /* The starting root is t, and the tree used is defined by rat */
1685 INCR_COUNT_SPLAY(bound_splay
);
1686 if (t
== NULL
) return t
;
1687 N
.left
= N
.right
= NULL
;
1691 comp
= compare(addr
, t
->start
, t
->size
);
1694 if (y
== NULL
) break;
1695 if (compare(addr
, y
->start
, y
->size
) < 0) {
1696 t
->left
= y
->right
; /* rotate right */
1699 if (t
->left
== NULL
) break;
1701 r
->left
= t
; /* link right */
1704 } else if (comp
> 0) {
1706 if (y
== NULL
) break;
1707 if (compare(addr
, y
->start
, y
->size
) > 0) {
1708 t
->right
= y
->left
; /* rotate left */
1711 if (t
->right
== NULL
) break;
1713 l
->right
= t
; /* link left */
1720 l
->right
= t
->left
; /* assemble */
1728 #define compare_end(start,tend) (start < tend ? -1 : \
1729 start > tend ? 1 : 0)
1731 static Tree
* splay_end (size_t addr
, Tree
*t
)
1732 /* Splay using the key start (which may or may not be in the tree.) */
1733 /* The starting root is t, and the tree used is defined by rat */
1738 INCR_COUNT_SPLAY(bound_splay_end
);
1739 if (t
== NULL
) return t
;
1740 N
.left
= N
.right
= NULL
;
1744 comp
= compare_end(addr
, t
->start
+ t
->size
);
1747 if (y
== NULL
) break;
1748 if (compare_end(addr
, y
->start
+ y
->size
) < 0) {
1749 t
->left
= y
->right
; /* rotate right */
1752 if (t
->left
== NULL
) break;
1754 r
->left
= t
; /* link right */
1757 } else if (comp
> 0) {
1759 if (y
== NULL
) break;
1760 if (compare_end(addr
, y
->start
+ y
->size
) > 0) {
1761 t
->right
= y
->left
; /* rotate left */
1764 if (t
->right
== NULL
) break;
1766 l
->right
= t
; /* link left */
1773 l
->right
= t
->left
; /* assemble */
1781 static Tree
* splay_insert(size_t addr
, size_t size
, Tree
* t
)
1782 /* Insert key start into the tree t, if it is not already there. */
1783 /* Return a pointer to the resulting tree. */
1787 INCR_COUNT_SPLAY(bound_splay_insert
);
1790 if (compare(addr
, t
->start
, t
->size
)==0) {
1791 return t
; /* it's already there */
1795 if (tree_free_list
) {
1796 new = tree_free_list
;
1797 tree_free_list
= new->left
;
1802 new = (Tree
*) BOUND_MALLOC (sizeof (Tree
));
1805 bound_alloc_error("not enough memory for bound checking code");
1809 new->left
= new->right
= NULL
;
1810 } else if (compare(addr
, t
->start
, t
->size
) < 0) {
1811 new->left
= t
->left
;
1815 new->right
= t
->right
;
1821 new->type
= TCC_TYPE_NONE
;
1822 new->is_invalid
= 0;
1827 #define compare_destroy(start,tstart) (start < tstart ? -1 : \
1828 start > tstart ? 1 : 0)
1830 static Tree
* splay_delete(size_t addr
, Tree
*t
)
1831 /* Deletes addr from the tree if it's there. */
1832 /* Return a pointer to the resulting tree. */
1836 INCR_COUNT_SPLAY(bound_splay_delete
);
1837 if (t
==NULL
) return NULL
;
1839 if (compare_destroy(addr
, t
->start
) == 0) { /* found it */
1840 if (t
->left
== NULL
) {
1843 x
= splay(addr
, t
->left
);
1844 x
->right
= t
->right
;
1847 t
->left
= tree_free_list
;
1854 return t
; /* It wasn't there */
1858 void splay_printtree(Tree
* t
, int d
)
1861 if (t
== NULL
) return;
1862 splay_printtree(t
->right
, d
+1);
1863 for (i
=0; i
<d
; i
++) fprintf(stderr
," ");
1864 fprintf(stderr
,"%p(0x%lx:%u:%u)\n",
1865 (void *) t
->start
, (unsigned long) t
->size
,
1866 (unsigned)t
->type
, (unsigned)t
->is_invalid
);
1867 splay_printtree(t
->left
, d
+1);