1/* 2 * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that: (1) source code distributions 7 * retain the above copyright notice and this paragraph in its entirety, (2) 8 * distributions including binary code include the above copyright notice and --- 8 unchanged lines hidden (view full) --- 17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 20 * 21 * Optimization module for tcpdump intermediate representation. 22 */ 23#ifndef lint 24static const char rcsid[] _U_ = |
25 "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.85.2.3 2007/09/12 21:29:45 guy Exp $ (LBL)"; |
26#endif 27 28#ifdef HAVE_CONFIG_H 29#include "config.h" 30#endif 31 32#include <stdio.h> 33#include <stdlib.h> --- 585 unchanged lines hidden (view full) --- 619 *valp = newval; 620} 621 622static void 623fold_op(s, v0, v1) 624 struct stmt *s; 625 int v0, v1; 626{ |
627 bpf_u_int32 a, b; |
628 629 a = vmap[v0].const_val; 630 b = vmap[v1].const_val; 631 632 switch (BPF_OP(s->code)) { 633 case BPF_ADD: 634 a += b; 635 break; --- 1182 unchanged lines hidden (view full) --- 1818} 1819 1820static void 1821intern_blocks(root) 1822 struct block *root; 1823{ 1824 struct block *p; 1825 int i, j; |
1826 int done1; /* don't shadow global */ |
1827 top: |
1828 done1 = 1; |
1829 for (i = 0; i < n_blocks; ++i) 1830 blocks[i]->link = 0; 1831 1832 mark_code(root); 1833 1834 for (i = n_blocks - 1; --i >= 0; ) { 1835 if (!isMarked(blocks[i])) 1836 continue; --- 7 unchanged lines hidden (view full) --- 1844 } 1845 } 1846 } 1847 for (i = 0; i < n_blocks; ++i) { 1848 p = blocks[i]; 1849 if (JT(p) == 0) 1850 continue; 1851 if (JT(p)->link) { |
1852 done1 = 0; |
1853 JT(p) = JT(p)->link; 1854 } 1855 if (JF(p)->link) { |
1856 done1 = 0; |
1857 JF(p) = JF(p)->link; 1858 } 1859 } |
1860 if (!done1) |
1861 goto top; 1862} 1863 1864static void 1865opt_cleanup() 1866{ 1867 free((void *)vnode_base); 1868 free((void *)vmap); --- 98 unchanged lines hidden (view full) --- 1967 int i, n, max_stmts; 1968 1969 /* 1970 * First, count the blocks, so we can malloc an array to map 1971 * block number to block. Then, put the blocks into the array. 1972 */ 1973 unMarkAll(); 1974 n = count_blocks(root); |
1975 blocks = (struct block **)calloc(n, sizeof(*blocks)); |
1976 if (blocks == NULL) 1977 bpf_error("malloc"); 1978 unMarkAll(); 1979 n_blocks = 0; 1980 number_blks_r(root); 1981 1982 n_edges = 2 * n_blocks; |
1983 edges = (struct edge **)calloc(n_edges, sizeof(*edges)); |
1984 if (edges == NULL) 1985 bpf_error("malloc"); 1986 1987 /* 1988 * The number of levels is bounded by the number of nodes. 1989 */ |
1990 levels = (struct block **)calloc(n_blocks, sizeof(*levels)); |
1991 if (levels == NULL) 1992 bpf_error("malloc"); 1993 1994 edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1; 1995 nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1; 1996 1997 /* XXX */ 1998 space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space) --- 30 unchanged lines hidden (view full) --- 2029 for (i = 0; i < n; ++i) 2030 max_stmts += slength(blocks[i]->stmts) + 1; 2031 /* 2032 * We allocate at most 3 value numbers per statement, 2033 * so this is an upper bound on the number of valnodes 2034 * we'll need. 2035 */ 2036 maxval = 3 * max_stmts; |
2037 vmap = (struct vmapinfo *)calloc(maxval, sizeof(*vmap)); 2038 vnode_base = (struct valnode *)calloc(maxval, sizeof(*vnode_base)); |
2039 if (vmap == NULL || vnode_base == NULL) 2040 bpf_error("malloc"); 2041} 2042 2043/* 2044 * Some pointers used to convert the basic block form of the code, 2045 * into the array form that BPF requires. 'fstart' will point to 2046 * the malloc'd array while 'ftail' is used during the recursive traversal. --- 72 unchanged lines hidden (view full) --- 2119 goto filled; 2120 } 2121 if (off == slen - 2) /*???*/ 2122 goto filled; 2123 2124 { 2125 int i; 2126 int jt, jf; |
2127 const char *ljerr = "%s for block-local relative jump: off=%d"; |
2128 2129#if 0 2130 printf("code=%x off=%d %x %x\n", src->s.code, 2131 off, src->s.jt, src->s.jf); 2132#endif 2133 2134 if (!src->s.jt || !src->s.jf) { 2135 bpf_error(ljerr, "no jmp destination", off); --- 75 unchanged lines hidden (view full) --- 2211 } 2212 return (1); 2213} 2214 2215 2216/* 2217 * Convert flowgraph intermediate representation to the 2218 * BPF array representation. Set *lenp to the number of instructions. |
2219 * 2220 * This routine does *NOT* leak the memory pointed to by fp. It *must 2221 * not* do free(fp) before returning fp; doing so would make no sense, 2222 * as the BPF array pointed to by the return value of icode_to_fcode() 2223 * must be valid - it's being returned for use in a bpf_program structure. 2224 * 2225 * If it appears that icode_to_fcode() is leaking, the problem is that 2226 * the program using pcap_compile() is failing to free the memory in 2227 * the BPF program when it's done - the leak is in the program, not in 2228 * the routine that happens to be allocating the memory. (By analogy, if 2229 * a program calls fopen() without ever calling fclose() on the FILE *, 2230 * it will leak the FILE structure; the leak is not in fopen(), it's in 2231 * the program.) Change the program to use pcap_freecode() when it's 2232 * done with the filter program. See the pcap man page. |
2233 */ 2234struct bpf_insn * 2235icode_to_fcode(root, lenp) 2236 struct block *root; 2237 int *lenp; 2238{ 2239 int n; 2240 struct bpf_insn *fp; --- 69 unchanged lines hidden --- |