Identifying the start and end of functions in a C program

Question

I am currently programming in C to find the complexity of functions in a program based on the number of lines in the functions. I will have to fopen an existing C file and proceed with the calculation. I know that there maybe some builtin tools for finding it. But still I want it to be programmed manually. Is there any specific method to find the start and end of the various functions in a C file?

What language are you using to write your analyzer? Because it's simply a parsing question, and different languages and environments have different tools. — StoryTeller - Unslander Monica, Dec 13 '12 at 11:43
Not really, at least not without implementing at least part of a C parser. The good news is that it's pretty easy to do with tools like [Lex](http://en.wikipedia.org/wiki/Lex_%28software%29) and [Yacc](http://en.wikipedia.org/wiki/Yacc) if you don't really care about the contents of the functions or that the function declarations are valid semantically. — Some programmer dude, Dec 13 '12 at 11:43
And by the way, the number of lines is a _very_ bad measure of function complexity. I can make a very long function that does something very simple and fast, or a one-liner containing an advanced loop taking lots of time. You could probably use something like [LLVM](http://llvm.org/) to parse the code and then extract more reliable statistics about complexity than just the line count. — Some programmer dude, Dec 13 '12 at 12:01

score 2 · Accepted Answer · answered Dec 13 '12 at 12:55

Run this through C preprocessor. This way you strip comments, unroll macros, include #includes etc. Unless you want complexity of the user-readable code, this will produce results much more true.
Remove fixed strings. Anything between "" goes, note escaped quote \" doesn't close the string.
Scan the file. First { increases count of functions and begins scanning the body of a function. Observe depth. { increases depth, } decreases, as depth reaches 0 another } is the end of the function. Next { will be a new function, but as you scan the outside, if before reaching next { or EOF you encounter a ; - cancel any data collected on the last piece. That wasn't a function, it was a struct, an union or something like that.

Thanks! The third point was very clear. But, I don't understand the second point. How does removing them will help? Also, how to run through preprocessor? — Gomathi, Dec 13 '12 at 14:19
@Gomathi: Parse `void a() { printf("{{{\"{\"{"); }` As for preprocessor, depends on your C compiler. For GCC, http://stackoverflow.com/questions/3916979/gcc-preprocessor — SF., Dec 13 '12 at 15:19

score 1 · Answer 2 · answered Dec 13 '12 at 12:40

I would recommend a 2-pass approach.

Pass 1: Remove any open or close braces inside comments (and optionally those in preprocessor directives).

Pass 2: Count open and close braces and whenever they match up (#open == #close) a function ends. The next open brace denotes the start of a new function.

This approach is not fail-safe. It may fail if the code contains preprocessor statements that violate good programming practice. If you encounter such code you may want to run your tool on the code after it has passed through the preprocessor stage.

cd80 · Answer 3 · 2022-02-25T00:04:13.160

I finally found a nice way to do this!
doxygen already does a lot of things to process functions and other things nicely.
generate doxygen conf like doxygen -g doxygen_conf
open the conf file with your favorite editor and set GENERATE_XML = YES. You might also wanna set RECURSIVE = YES and others needed for your project, and run doxygen. set also INPUT = [PATH_TO_PROJECT_BASE]. In your doxygen build directory, you will find html/ and xml/.

cd80@cd80 ~/lab/VulnVizOnLinux/linux-5.4.109 » cd build_doc
cd80@cd80 ~/lab/VulnVizOnLinux/linux-5.4.109/build_doc » ls
ExtractFunctions.ipynb  html  xml
cd80@cd80 ~/lab/VulnVizOnLinux/linux-5.4.109/build_doc »

(ignore ExtractFunctions.ipynb, that's mine)
cd to xml and open any of xml files and analyze it for a while.
Here's how I did it.

import os
import xml.etree.ElementTree as ET

base_path = '/home/cd80/lab/VulnVizOnLinux/linux-5.4.109/'
open_files = {}
doc = ET.parse('/home/cd80/lab/VulnVizOnLinux/linux-5.4.109/build_doc/xml/4_2kernel_2module-plts_8c.xml')
root = doc.getroot()

for func in root.findall(".//memberdef/[@kind='function']"):
    name = func.find('./name').text
    location = func.find('./location')
    if 'bodyend' not in location.keys():
        continue # this memberdef is not a definition of function
    bodystart = int(location.attrib.get('bodystart'))
    bodyend = int(location.attrib.get('bodyend'))
    file_path = location.attrib.get('file')
    file_path = os.path.join(base_path, file_path)
    
    if file_path not in open_files.keys():
        with open(file_path, 'rb') as f:
            code = f.read().decode('utf-8')
        open_files[file_path] = code
    else:
        code = open_files[file_path]
    
    func_def = '\n'.join(code.split("\n")[bodystart-1:bodyend])
    print(func_def)
    print('='*30)

Result:

static struct plt_entry __get_adrp_add_pair(u64 dst, u64 pc,
                        enum aarch64_insn_register reg)
{
    u32 adrp, add;

    adrp = aarch64_insn_gen_adr(pc, dst, reg, AARCH64_INSN_ADR_TYPE_ADRP);
    add = aarch64_insn_gen_add_sub_imm(reg, reg, dst % SZ_4K,
                       AARCH64_INSN_VARIANT_64BIT,
                       AARCH64_INSN_ADSB_ADD);

    return (struct plt_entry){ cpu_to_le32(adrp), cpu_to_le32(add) };
}
==============================
struct plt_entry get_plt_entry(u64 dst, void *pc)
{
    struct plt_entry plt;
    static u32 br;

    if (!br)
        br = aarch64_insn_gen_branch_reg(AARCH64_INSN_REG_16,
                         AARCH64_INSN_BRANCH_NOLINK);

    plt = __get_adrp_add_pair(dst, (u64)pc, AARCH64_INSN_REG_16);
    plt.br = cpu_to_le32(br);

    return plt;
}
==============================
bool plt_entries_equal(const struct plt_entry *a, const struct plt_entry *b)
{
    u64 p, q;

    /*
     * Check whether both entries refer to the same target:
     * do the cheapest checks first.
     * If the 'add' or 'br' opcodes are different, then the target
     * cannot be the same.
     */
    if (a->add != b->add || a->br != b->br)
        return false;

    p = ALIGN_DOWN((u64)a, SZ_4K);
    q = ALIGN_DOWN((u64)b, SZ_4K);

    /*
     * If the 'adrp' opcodes are the same then we just need to check
     * that they refer to the same 4k region.
     */
    if (a->adrp == b->adrp && p == q)
        return true;

    return (p + aarch64_insn_adrp_get_offset(le32_to_cpu(a->adrp))) ==
           (q + aarch64_insn_adrp_get_offset(le32_to_cpu(b->adrp)));
}
==============================
static bool in_init(const struct module *mod, void *loc)
{
    return (u64)loc - (u64)mod->init_layout.base < mod->init_layout.size;
}
==============================
u64 module_emit_plt_entry(struct module *mod, Elf64_Shdr *sechdrs,
              void *loc, const Elf64_Rela *rela,
              Elf64_Sym *sym)
{
    struct mod_plt_sec *pltsec = !in_init(mod, loc) ? &mod->arch.core :
                              &mod->arch.init;
    struct plt_entry *plt = (struct plt_entry *)sechdrs[pltsec->plt_shndx].sh_addr;
    int i = pltsec->plt_num_entries;
    int j = i - 1;
    u64 val = sym->st_value + rela->r_addend;

    if (is_forbidden_offset_for_adrp(&plt[i].adrp))
        i++;

    plt[i] = get_plt_entry(val, &plt[i]);

    /*
     * Check if the entry we just created is a duplicate. Given that the
     * relocations are sorted, this will be the last entry we allocated.
     * (if one exists).
     */
    if (j >= 0 && plt_entries_equal(plt + i, plt + j))
        return (u64)&plt[j];

    pltsec->plt_num_entries += i - j;
    if (WARN_ON(pltsec->plt_num_entries > pltsec->plt_max_entries))
        return 0;

    return (u64)&plt[i];
}
==============================
static int cmp_rela(const void *a, const void *b)
{
    const Elf64_Rela *x = a, *y = b;
    int i;

    /* sort by type, symbol index and addend */
    i = cmp_3way(ELF64_R_TYPE(x->r_info), ELF64_R_TYPE(y->r_info));
    if (i == 0)
        i = cmp_3way(ELF64_R_SYM(x->r_info), ELF64_R_SYM(y->r_info));
    if (i == 0)
        i = cmp_3way(x->r_addend, y->r_addend);
    return i;
}
==============================
static bool duplicate_rel(const Elf64_Rela *rela, int num)
{
    /*
     * Entries are sorted by type, symbol index and addend. That means
     * that, if a duplicate entry exists, it must be in the preceding
     * slot.
     */
    return num > 0 && cmp_rela(rela + num, rela + num - 1) == 0;
}
==============================
static unsigned int count_plts(Elf64_Sym *syms, Elf64_Rela *rela, int num,
                   Elf64_Word dstidx, Elf_Shdr *dstsec)
{
    unsigned int ret = 0;
    Elf64_Sym *s;
    int i;

    for (i = 0; i < num; i++) {
        u64 min_align;

        switch (ELF64_R_TYPE(rela[i].r_info)) {
        case R_AARCH64_JUMP26:
        case R_AARCH64_CALL26:
            if (!IS_ENABLED(CONFIG_RANDOMIZE_BASE))
                break;

            /*
             * We only have to consider branch targets that resolve
             * to symbols that are defined in a different section.
             * This is not simply a heuristic, it is a fundamental
             * limitation, since there is no guaranteed way to emit
             * PLT entries sufficiently close to the branch if the
             * section size exceeds the range of a branch
             * instruction. So ignore relocations against defined
             * symbols if they live in the same section as the
             * relocation target.
             */
            s = syms + ELF64_R_SYM(rela[i].r_info);
            if (s->st_shndx == dstidx)
                break;

            /*
             * Jump relocations with non-zero addends against
             * undefined symbols are supported by the ELF spec, but
             * do not occur in practice (e.g., 'jump n bytes past
             * the entry point of undefined function symbol f').
             * So we need to support them, but there is no need to
             * take them into consideration when trying to optimize
             * this code. So let's only check for duplicates when
             * the addend is zero: this allows us to record the PLT
             * entry address in the symbol table itself, rather than
             * having to search the list for duplicates each time we
             * emit one.
             */
            if (rela[i].r_addend != 0 || !duplicate_rel(rela, i))
                ret++;
            break;
        case R_AARCH64_ADR_PREL_PG_HI21_NC:
        case R_AARCH64_ADR_PREL_PG_HI21:
            if (!IS_ENABLED(CONFIG_ARM64_ERRATUM_843419) ||
                !cpus_have_const_cap(ARM64_WORKAROUND_843419))
                break;

            /*
             * Determine the minimal safe alignment for this ADRP
             * instruction: the section alignment at which it is
             * guaranteed not to appear at a vulnerable offset.
             *
             * This comes down to finding the least significant zero
             * bit in bits [11:3] of the section offset, and
             * increasing the section's alignment so that the
             * resulting address of this instruction is guaranteed
             * to equal the offset in that particular bit (as well
             * as all less signficant bits). This ensures that the
             * address modulo 4 KB != 0xfff8 or 0xfffc (which would
             * have all ones in bits [11:3])
             */
            min_align = 2ULL << ffz(rela[i].r_offset | 0x7);

            /*
             * Allocate veneer space for each ADRP that may appear
             * at a vulnerable offset nonetheless. At relocation
             * time, some of these will remain unused since some
             * ADRP instructions can be patched to ADR instructions
             * instead.
             */
            if (min_align > SZ_4K)
                ret++;
            else
                dstsec->sh_addralign = max(dstsec->sh_addralign,
                               min_align);
            break;
        }
    }

    if (IS_ENABLED(CONFIG_ARM64_ERRATUM_843419) &&
        cpus_have_const_cap(ARM64_WORKAROUND_843419))
        /*
         * Add some slack so we can skip PLT slots that may trigger
         * the erratum due to the placement of the ADRP instruction.
         */
        ret += DIV_ROUND_UP(ret, (SZ_4K / sizeof(struct plt_entry)));

    return ret;
}
==============================
int module_frob_arch_sections(Elf_Ehdr *ehdr, Elf_Shdr *sechdrs,
                  char *secstrings, struct module *mod)
{
    unsigned long core_plts = 0;
    unsigned long init_plts = 0;
    Elf64_Sym *syms = NULL;
    Elf_Shdr *pltsec, *tramp = NULL;
    int i;

    /*
     * Find the empty .plt section so we can expand it to store the PLT
     * entries. Record the symtab address as well.
     */
    for (i = 0; i < ehdr->e_shnum; i++) {
        if (!strcmp(secstrings + sechdrs[i].sh_name, ".plt"))
            mod->arch.core.plt_shndx = i;
        else if (!strcmp(secstrings + sechdrs[i].sh_name, ".init.plt"))
            mod->arch.init.plt_shndx = i;
        else if (!strcmp(secstrings + sechdrs[i].sh_name,
                 ".text.ftrace_trampoline"))
            tramp = sechdrs + i;
        else if (sechdrs[i].sh_type == SHT_SYMTAB)
            syms = (Elf64_Sym *)sechdrs[i].sh_addr;
    }

    if (!mod->arch.core.plt_shndx || !mod->arch.init.plt_shndx) {
        pr_err("%s: module PLT section(s) missing\n", mod->name);
        return -ENOEXEC;
    }
    if (!syms) {
        pr_err("%s: module symtab section missing\n", mod->name);
        return -ENOEXEC;
    }

    for (i = 0; i < ehdr->e_shnum; i++) {
        Elf64_Rela *rels = (void *)ehdr + sechdrs[i].sh_offset;
        int numrels = sechdrs[i].sh_size / sizeof(Elf64_Rela);
        Elf64_Shdr *dstsec = sechdrs + sechdrs[i].sh_info;

        if (sechdrs[i].sh_type != SHT_RELA)
            continue;

        /* ignore relocations that operate on non-exec sections */
        if (!(dstsec->sh_flags & SHF_EXECINSTR))
            continue;

        /* sort by type, symbol index and addend */
        sort(rels, numrels, sizeof(Elf64_Rela), cmp_rela, NULL);

        if (!str_has_prefix(secstrings + dstsec->sh_name, ".init"))
            core_plts += count_plts(syms, rels, numrels,
                        sechdrs[i].sh_info, dstsec);
        else
            init_plts += count_plts(syms, rels, numrels,
                        sechdrs[i].sh_info, dstsec);
    }

    pltsec = sechdrs + mod->arch.core.plt_shndx;
    pltsec->sh_type = SHT_NOBITS;
    pltsec->sh_flags = SHF_EXECINSTR | SHF_ALLOC;
    pltsec->sh_addralign = L1_CACHE_BYTES;
    pltsec->sh_size = (core_plts  + 1) * sizeof(struct plt_entry);
    mod->arch.core.plt_num_entries = 0;
    mod->arch.core.plt_max_entries = core_plts;

    pltsec = sechdrs + mod->arch.init.plt_shndx;
    pltsec->sh_type = SHT_NOBITS;
    pltsec->sh_flags = SHF_EXECINSTR | SHF_ALLOC;
    pltsec->sh_addralign = L1_CACHE_BYTES;
    pltsec->sh_size = (init_plts + 1) * sizeof(struct plt_entry);
    mod->arch.init.plt_num_entries = 0;
    mod->arch.init.plt_max_entries = init_plts;

    if (tramp) {
        tramp->sh_type = SHT_NOBITS;
        tramp->sh_flags = SHF_EXECINSTR | SHF_ALLOC;
        tramp->sh_addralign = __alignof__(struct plt_entry);
        tramp->sh_size = sizeof(struct plt_entry);
    }

    return 0;
}
==============================

Dirty but works just as how I wanted

Identifying the start and end of functions in a C program

3 Answers3