1/*
2
3  Copyright (C) 2005 Silicon Graphics, Inc.  All Rights Reserved.
4
5  This program is free software; you can redistribute it and/or modify it
6  under the terms of version 2.1 of the GNU Lesser General Public License
7  as published by the Free Software Foundation.
8
9  This program is distributed in the hope that it would be useful, but
10  WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13  Further, this software is distributed without any warranty that it is
14  free of the rightful claim of any third person regarding infringement
15  or the like.  Any license provided herein, whether implied or
16  otherwise, applies only to this software file.  Patent licenses, if
17  any, provided herein do not apply to combinations of this program with
18  other software, or any other product whatsoever.
19
20  You should have received a copy of the GNU Lesser General Public
21  License along with this program; if not, write the Free Software
22  Foundation, Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307,
23  USA.
24
25  Contact information:  Silicon Graphics, Inc., 1500 Crittenden Lane,
26  Mountain View, CA 94043, or:
27
28  http://www.sgi.com
29
30  For further information regarding this notice, see:
31
32  http://oss.sgi.com/projects/GenInfo/NoticeExplan
33
34*/
35
36
37
38/* malloc_check.c For checking dealloc completeness.
39
40   This code is as simple as possible and works ok for
41   reasonable size allocation counts.
42
43   It treats allocation as global, and so will not
44   work very well if an application opens more than one
45   Dwarf_Debug.
46
47*/
48
49#include <stdio.h>
50#include <stdlib.h>		/* for exit() and various malloc
51				   prototypes */
52#include "config.h"
53#include "dwarf_incl.h"
54#include "malloc_check.h"
55#ifdef  WANT_LIBBDWARF_MALLOC_CHECK
56
57/* To turn off printing every entry, just change the define
58   to set PRINT_MALLOC_DETAILS 0.
59*/
60#define PRINT_MALLOC_DETAILS 0
61
62#define MC_TYPE_UNKNOWN 0
63#define MC_TYPE_ALLOC 1
64#define MC_TYPE_DEALLOC 2
65
66struct mc_data_s {
67    struct mc_data_s *mc_prev;
68    unsigned long mc_address;	/* Assumes this is large enough to hold
69				   a pointer! */
70
71    long mc_alloc_number;	/* Assigned in order by when record
72				   created. */
73    unsigned char mc_alloc_code;	/* Allocation code, libdwarf. */
74    unsigned char mc_type;
75    unsigned char mc_dealloc_noted;	/* Used on an ALLOC node. */
76    unsigned char mc_dealloc_noted_count;	/* Used on an ALLOC
77						   node. */
78};
79
80/*
81
82
83*/
84#define HASH_TABLE_SIZE 10501
85static struct mc_data_s *mc_data_hash[HASH_TABLE_SIZE];
86static long mc_data_list_size = 0;
87
88static char *alloc_type_name[MAX_DW_DLA + 1] = {
89    "",
90    "DW_DLA_STRING",
91    "DW_DLA_LOC",
92    "DW_DLA_LOCDESC",
93    "DW_DLA_ELLIST",
94    "DW_DLA_BOUNDS",
95    "DW_DLA_BLOCK",
96    "DW_DLA_DEBUG",
97    "DW_DLA_DIE",
98    "DW_DLA_LINE",
99    "DW_DLA_ATTR",
100    "DW_DLA_TYPE",
101    "DW_DLA_SUBSCR",
102    "DW_DLA_GLOBAL",
103    "DW_DLA_ERROR",
104    "DW_DLA_LIST",
105    "DW_DLA_LINEBUF",
106    "DW_DLA_ARANGE",
107    "DW_DLA_ABBREV",
108    "DW_DLA_FRAME_OP",
109    "DW_DLA_CIE",
110    "DW_DLA_FDE",
111    "DW_DLA_LOC_BLOCK",
112    "DW_DLA_FRAME_BLOCK",
113    "DW_DLA_FUNC",
114    "DW_DLA_TYPENAME",
115    "DW_DLA_VAR",
116    "DW_DLA_WEAK",
117    "DW_DLA_ADDR",
118    "DW_DLA_ABBREV_LIST",
119    "DW_DLA_CHAIN",
120    "DW_DLA_CU_CONTEXT",
121    "DW_DLA_FRAME",
122    "DW_DLA_GLOBAL_CONTEXT",
123    "DW_DLA_FILE_ENTRY",
124    "DW_DLA_LINE_CONTEXT",
125    "DW_DLA_LOC_CHAIN",
126    "DW_DLA_HASH_TABLE",
127    "DW_DLA_FUNC_CONTEXT",
128    "DW_DLA_TYPENAME_CONTEXT",
129    "DW_DLA_VAR_CONTEXT",
130    "DW_DLA_WEAK_CONTEXT",
131    "DW_DLA_PUBTYPES_CONTEXT"
132	/* Don't forget to expand this list if the list of codes
133	   expands. */
134};
135
136static unsigned
137hash_address(unsigned long addr)
138{
139    unsigned long a = addr >> 2;
140
141    return a % HASH_TABLE_SIZE;
142}
143
144#if PRINT_MALLOC_DETAILS
145static void
146print_alloc_dealloc_detail(unsigned long addr,
147			   int code, char *whichisit)
148{
149    fprintf(stderr,
150	    "%s  addr 0x%lx code %d (%s) entry %ld\n",
151	    whichisit, addr, code, alloc_type_name[code],
152	    mc_data_list_size);
153}
154#else
155#define  print_alloc_dealloc_detail(a,b,c)	/* nothing */
156#endif
157
158/* Create a zeroed struct or die. */
159static void *
160newone(void)
161{
162    struct mc_data_s *newd = malloc(sizeof(struct mc_data_s));
163
164    if (newd == 0) {
165	fprintf(stderr, "out of memory , # %ld\n", mc_data_list_size);
166	exit(1);
167    }
168    memset(newd, 0, sizeof(struct mc_data_s));
169    return newd;
170}
171
172/* Notify checker that get_alloc has allocated user data. */
173void
174dwarf_malloc_check_alloc_data(void *addr_in, unsigned char code)
175{
176    struct mc_data_s *newd = newone();
177    unsigned long addr = (unsigned long) addr_in;
178    struct mc_data_s **base = &mc_data_hash[hash_address(addr)];
179
180    print_alloc_dealloc_detail(addr, code, "alloc   ");
181    newd->mc_address = addr;
182    newd->mc_alloc_code = code;
183    newd->mc_type = MC_TYPE_ALLOC;
184    newd->mc_alloc_number = mc_data_list_size;
185    newd->mc_prev = *base;
186    *base = newd;
187    newd->mc_alloc_number = mc_data_list_size;
188    mc_data_list_size += 1;
189}
190
191static void
192print_entry(char *msg, struct mc_data_s *data)
193{
194    fprintf(stderr,
195	    "%s: 0x%08lx code %2d (%s) type %s dealloc noted %u ct %u\n",
196	    msg,
197	    (long) data->mc_address,
198	    data->mc_alloc_code,
199	    alloc_type_name[data->mc_alloc_code],
200	    (data->mc_type == MC_TYPE_ALLOC) ? "alloc  " :
201	    (data->mc_type == MC_TYPE_DEALLOC) ? "dealloc" : "unknown",
202	    (unsigned) data->mc_dealloc_noted,
203	    (unsigned) data->mc_dealloc_noted_count);
204}
205
206/* newd is a 'dealloc'.
207*/
208static long
209balanced_by_alloc_p(struct mc_data_s *newd,
210		    long *addr_match_num,
211		    struct mc_data_s **addr_match,
212		    struct mc_data_s *base)
213{
214    struct mc_data_s *cur = base;
215
216    for (; cur; cur = cur->mc_prev) {
217	if (cur->mc_address == newd->mc_address) {
218	    if (cur->mc_type == MC_TYPE_ALLOC) {
219		if (cur->mc_alloc_code == newd->mc_alloc_code) {
220		    *addr_match = cur;
221		    *addr_match_num = cur->mc_alloc_number;
222		    return cur->mc_alloc_number;
223		} else {
224		    /* code mismatch */
225		    *addr_match = cur;
226		    *addr_match_num = cur->mc_alloc_number;
227		    return -1;
228		}
229	    } else {
230		/* Unbalanced new/del */
231		*addr_match = cur;
232		*addr_match_num = cur->mc_alloc_number;
233		return -1;
234	    }
235	}
236    }
237    return -1;
238}
239
240/*  A dealloc is to take place. Ensure it balances an alloc.
241*/
242void
243dwarf_malloc_check_dealloc_data(void *addr_in, unsigned char code)
244{
245    struct mc_data_s *newd = newone();
246    long prev;
247    long addr_match_num = -1;
248    struct mc_data_s *addr_match = 0;
249    unsigned long addr = (unsigned long) addr_in;
250    struct mc_data_s **base = &mc_data_hash[hash_address(addr)];
251
252
253    print_alloc_dealloc_detail(addr, code, "dealloc ");
254    newd->mc_address = (unsigned long) addr;
255    newd->mc_alloc_code = code;
256    newd->mc_type = MC_TYPE_DEALLOC;
257    newd->mc_prev = *base;
258    prev =
259	balanced_by_alloc_p(newd, &addr_match_num, &addr_match, *base);
260    if (prev < 0) {
261	fprintf(stderr,
262		"Unbalanced dealloc at index %ld\n", mc_data_list_size);
263	print_entry("new", newd);
264	fprintf(stderr, "addr-match_num? %ld\n", addr_match_num);
265	if (addr_match) {
266	    print_entry("prev entry", addr_match);
267	    if (addr_match->mc_dealloc_noted > 1) {
268		fprintf(stderr, "Above is Duplicate dealloc!\n");
269	    }
270	}
271	abort();
272	exit(3);
273    }
274    addr_match->mc_dealloc_noted = 1;
275    addr_match->mc_dealloc_noted_count += 1;
276    if (addr_match->mc_dealloc_noted_count > 1) {
277	fprintf(stderr, "Double dealloc entry %ld\n", addr_match_num);
278	print_entry("new dealloc entry", newd);
279	print_entry("bad alloc entry", addr_match);
280    }
281    *base = newd;
282    mc_data_list_size += 1;
283}
284
285/* Final check for leaks.
286*/
287void
288dwarf_malloc_check_complete(char *msg)
289{
290    long i = 0;
291    long total = mc_data_list_size;
292    long hash_slots_used = 0;
293    long max_chain_length = 0;
294
295    fprintf(stderr, "Run complete, %s. %ld entries\n", msg, total);
296    for (; i < HASH_TABLE_SIZE; ++i) {
297	struct mc_data_s *cur = mc_data_hash[i];
298	long cur_chain_length = 0;
299
300	if (cur == 0)
301	    continue;
302	++hash_slots_used;
303	for (; cur; cur = cur->mc_prev) {
304	    ++cur_chain_length;
305	    if (cur->mc_type == MC_TYPE_ALLOC) {
306		if (cur->mc_dealloc_noted) {
307		    if (cur->mc_dealloc_noted > 1) {
308			fprintf(stderr,
309				" Duplicate dealloc! entry %ld\n",
310				cur->mc_alloc_number);
311			print_entry("duplicate dealloc", cur);
312
313		    }
314		    continue;
315		} else {
316		    fprintf(stderr, "malloc no dealloc, entry %ld\n",
317			    cur->mc_alloc_number);
318		    print_entry("dangle", cur);
319		}
320	    } else {
321		/* mc_type is MC_TYPE_DEALLOC, already checked */
322
323	    }
324	}
325	if (cur_chain_length > max_chain_length) {
326	    max_chain_length = cur_chain_length;
327	}
328    }
329    fprintf(stderr, "mc hash table slots=%ld, "
330	    "used=%ld,  maxchain=%ld\n",
331	    (long) HASH_TABLE_SIZE, hash_slots_used, max_chain_length);
332    return;
333}
334
335#endif /* WANT_LIBBDWARF_MALLOC_CHECK */
336