I was playing a bit around to see if it is possible to figure out if a variable is accessed without holding the corresponding lock. This never got anywhere and that's why I abandon it. In case someone wants to use parts of it or whatever, please be my guest.
Example output: ./test-locks validation/caps.c validation/caps.c:49:13: warning: function 'set_str' not holding 'anon' validation/caps.c:25:13: warning: leaks lock 'anon' frame: ep 0x7f0af437e010 a frame: ep 0x7f0af437e0a0 okay1 (call a) frame: ep 0x7f0af437e0d0 bad2 (call okay1) validation/caps.c:70:8: warning: leaks lock 'global_lock' frame: ep 0x7f0af437e100 wtf_lock frame: ep 0x7f0af437e1f0 bad4 (call wtf_lock, global_lock) Signed-off-by: Daniel Wagner <[email protected]> --- Makefile | 3 +- lib.c | 2 + lib.h | 7 + test-locks.c | 1020 +++++++++++++++++++++++++++++++++++++++++++++++++++++ validation/caps.c | 80 +++++ 5 files changed, 1111 insertions(+), 1 deletion(-) create mode 100644 test-locks.c create mode 100644 validation/caps.c diff --git a/Makefile b/Makefile index c7031af..db0c343 100644 --- a/Makefile +++ b/Makefile @@ -54,7 +54,8 @@ INCLUDEDIR=$(PREFIX)/include PKGCONFIGDIR=$(LIBDIR)/pkgconfig PROGRAMS=test-lexing test-parsing obfuscate compile graph sparse \ - test-linearize example test-unssa test-dissect ctags + test-linearize example test-unssa test-dissect ctags \ + test-locks INST_PROGRAMS=sparse cgcc INST_MAN1=sparse.1 cgcc.1 diff --git a/lib.c b/lib.c index 8dc5bcf..7b49e2f 100644 --- a/lib.c +++ b/lib.c @@ -244,6 +244,7 @@ int Wvla = 1; int dbg_entry = 0; int dbg_dead = 0; +int dbg_caps = 0; int preprocess_only; @@ -518,6 +519,7 @@ static char **handle_switch_W(char *arg, char **next) static struct warning debugs[] = { { "entry", &dbg_entry}, { "dead", &dbg_dead}, + { "caps", &dbg_caps}, }; diff --git a/lib.h b/lib.h index 15b69fa..87d1948 100644 --- a/lib.h +++ b/lib.h @@ -130,6 +130,7 @@ extern int Wvla; extern int dbg_entry; extern int dbg_dead; +extern int dbg_caps; extern int arch_m64; @@ -189,6 +190,12 @@ static inline struct basic_block *first_basic_block(struct basic_block_list *hea { return first_ptr_list((struct ptr_list *)head); } + +static inline struct basic_block *last_basic_block(struct basic_block_list *head) +{ + return last_ptr_list((struct ptr_list *)head); +} + static inline struct instruction *last_instruction(struct instruction_list *head) { return last_ptr_list((struct ptr_list *)head); diff --git a/test-locks.c b/test-locks.c new file mode 100644 index 0000000..f311f4c --- /dev/null +++ b/test-locks.c @@ -0,0 +1,1020 @@ +/* + * This is an miserable attempt in static code analysis. The test + * executes the program and maintains a current set of locks. At every + * function entry and exit point all the current lock set is attached + * to the function and the current calling stack is also added to the lock. + * + * In the second phase the check_leaking() function then looks at all + * locks and the calling stacks and reports all those function which + * have an lock in the exit lock set and no other function is calling them. + * Obvioysly reallity is much more complex and this simple testing + * will not catch a lot of wrong cases. + * + * There is also the attempt to figure out if a variable has been accessed + * without holding the corresponding lock. + * + * If you want to understand what is doing run it with + * + * $ test-locks validation/caps.c -vcaps -v -v -v + * + * which print a lot of details. + * + * Copyright (C) 2016 BMW Car IT GmbH. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#include <stdarg.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <unistd.h> +#include <fcntl.h> + +#include "lib.h" +#include "allocate.h" +#include "token.h" +#include "parse.h" +#include "symbol.h" +#include "expression.h" +#include "linearize.h" +#include "flow.h" +#include "scope.h" + +#define dbg_level0 (dbg_caps) +#define dbg_level1 (dbg_caps && verbose > 0) +#define dbg_level2 (dbg_caps && verbose > 1) +#define dbg_level3 (dbg_caps && verbose > 2) + +struct frame { + struct instruction *insn; + struct entrypoint *ep; +}; + +ALLOCATOR(frame, "call stack"); +DECLARE_PTR_LIST(frame_list, struct frame); + +struct frame *alloc_frame(struct entrypoint *ep, struct instruction *insn) +{ + struct frame *frame = __alloc_frame(0); + + frame->ep = ep; + frame->insn = insn; + return frame; +} + +static inline struct frame *last_frame(struct frame_list *head) +{ + return last_ptr_list((struct ptr_list *)head); +} + +static inline struct frame *first_frame(struct frame_list *head) +{ + return first_ptr_list((struct ptr_list *)head); +} + +static inline struct frame *delete_last_frame(struct frame_list **head) +{ + return delete_ptr_list_last((struct ptr_list **)head); +} + +static inline void add_frame(struct frame_list **list, struct frame *frame) +{ + add_ptr_list(list, frame); +} + +static inline struct frame *lookup_frame(struct frame_list *list, + struct entrypoint *ep) +{ + struct frame *c; + + FOR_EACH_PTR(list, c) { + if (c->ep == ep) + return c; + } END_FOR_EACH_PTR(c); + + return NULL; +} + +static inline int frame_list_size(struct frame_list *head) +{ + return ptr_list_size((struct ptr_list *)head); +} + +static inline int frame_cmp(struct frame *f1, struct frame *f2) +{ + return !(f1->ep == f2->ep && f1->insn == f2->insn); +} + +static int stack_cmp(struct frame_list *s1, struct frame_list *s2) +{ + struct frame *f1, *f2; + + PREPARE_PTR_LIST(s1, f1); + PREPARE_PTR_LIST(s2, f2); + for (;;) { + if (!f1 || !f2) + return 1; + + if (frame_cmp(f1, f2)) + return 1; + + NEXT_PTR_LIST(f1); + NEXT_PTR_LIST(f2); + } + FINISH_PTR_LIST(f2); + FINISH_PTR_LIST(f1); + + return 0; +} + +static int stack_frame_position(struct frame_list *stack, struct entrypoint *ep) +{ + struct frame *f; + int pos = 0; + + FOR_EACH_PTR(stack, f) { + if (f->ep == ep) + return pos; + pos++; + } END_FOR_EACH_PTR(f); + + return -1; +} + +static void copy_stack(struct frame_list *from, struct frame_list **to) +{ + struct frame *c; + + FOR_EACH_PTR(from, c) { + add_frame(to, alloc_frame(c->ep, c->insn)); + } END_FOR_EACH_PTR(c); +} + +/* Better naming wouldn't hurt. we could also do a frame_list** in + * struct lock but that is really hard to read. Let's wrap it here and + * use it as 2 dimensional list. + */ +struct stack { + struct frame_list *stack; +}; +ALLOCATOR(stack, "stack list"); +DECLARE_PTR_LIST(stack_list, struct stack); + +static inline void add_stack(struct stack_list **list, struct stack *stack) +{ + add_ptr_list(list, stack); +} + +struct lock { + unsigned int ref; + struct symbol *sym; + struct capability_list *caps; + struct stack_list *stacks; +}; + +ALLOCATOR(lock, "lock list"); +DECLARE_PTR_LIST(lock_list, struct lock); + +static struct lock *alloc_lock(struct symbol *sym) +{ + struct lock *lock = __alloc_lock(0); + + lock->ref = 1; + lock->sym = sym; + + return lock; +}; + +static inline void ref_lock(struct lock *lock) +{ + lock->ref++; +} + +static inline unsigned int unref_lock(struct lock *lock) +{ + return --lock->ref; +} + +static inline void add_lock(struct lock_list **list, struct lock *lock) +{ + add_ptr_list(list, lock); +} + +static inline void remove_lock(struct lock_list **list, struct lock *lock) +{ + delete_ptr_list_entry((struct ptr_list **)list, lock, 1); +} + +static struct lock *lookup_lock(struct lock_list *list, struct symbol *sym) +{ + struct lock *l; + + FOR_EACH_PTR(list, l) { + if (sym == l->sym) + return l; + } END_FOR_EACH_PTR(l); + + return NULL; +} + +static struct lock_list *all_locks; + +static void add_stack_trace(struct frame_list *stack, struct lock *lock) +{ + struct stack *st; + + /* Filter out duplicates */ + FOR_EACH_PTR(lock->stacks, st) { + if (!stack_cmp(stack, st->stack)) + return; + } END_FOR_EACH_PTR(st); + + st = __alloc_stack(0); + copy_stack(stack, &st->stack); + add_stack(&lock->stacks, st); +} + +/* Copy the current lock set to either the entry or exit list of the + * function. Remember also the calling stack. This will be handy + * in the second step of the analysis when we check for leaking + * locks etc. + */ +static void copy_lock_list(struct frame_list *stack, + struct lock_list *from, struct lock_list **to) +{ + struct lock *lock, *l; + + FOR_EACH_PTR(from, lock) { + /* let's colapse symbols with the same addresse to one + * lock and remove duplicates by this. + */ + l = lookup_lock(all_locks, lock->sym); + if (!l) { + l = alloc_lock(lock->sym); + add_lock(&all_locks, l); + } else + ref_lock(l); + + if (!lookup_lock(*to, lock->sym)) + add_lock(to, l); + + add_stack_trace(stack, l); + } END_FOR_EACH_PTR(lock); +} + +static inline int lock_list_size(struct lock_list *list) +{ + return ptr_list_size((struct ptr_list *)list); +} + +struct bb_info { + struct lock_list *entry; + struct lock_list *exit; +}; +ALLOCATOR(bb_info, "bb info"); + +/* debug printfs helpers */ + +static void show_call_stack(struct frame_list *list, int level) +{ + struct frame *c; + + FOR_EACH_PTR_REVERSE(list, c) { + printf("%*sframe: ep %p %s", level * 2, "", c->ep, + show_ident(c->ep->name->ident)); + if (c->insn) + printf(" (%s)", show_instruction(c->insn)); + printf("\n"); + } END_FOR_EACH_PTR_REVERSE(c); +} + +static void show_short_symbol_list(struct symbol_list *list, const char *name) +{ + struct symbol *sym; + const char *prepend = ""; + + printf("%s:\t", name); + FOR_EACH_PTR(list, sym) { + printf("%s", prepend); + prepend = ", "; + printf("%s", show_ident(sym->ident)); + } END_FOR_EACH_PTR(sym); + puts(""); +} + +static void show_pseudo_user_list(struct pseudo_user_list *list, + const char *name) +{ + struct pseudo_user *pu; + + if (ptr_list_empty(list)) + return; + printf("%s:\n", name); + FOR_EACH_PTR(list, pu) { + printf("\t%s used by %p, %s\n", + show_pseudo(*pu->userp), pu->insn, + show_instruction(pu->insn)); + } END_FOR_EACH_PTR(pu); +} + +static void show_pseudo_list(struct pseudo_list *list, const char *name) +{ + struct pseudo *p; + struct symbol *s; + + printf("%s:\n", name); + FOR_EACH_PTR(list, p) { + printf("\t%s", show_pseudo(p)); + switch (p->type) { + case PSEUDO_SYM: + printf(" (symbol %p scope %p ", p->sym, p->sym->scope); + s = p->sym->next_id; + while (s) { + printf("next_id %p ", s); + s = s->next_id; + } + show_type(p->sym); + printf(")\n"); + break; + case PSEUDO_ARG: + printf(" ("); + show_pseudo_user_list(p->users, "users"); + printf(" )\n"); + break; + default: + break; + } + } END_FOR_EACH_PTR(p); +} + +static void show_basic_block_list(struct basic_block_list *list, + const char *name) +{ + struct basic_block *bb; + const char *prepend = ""; + + printf("%s:\t", name); + FOR_EACH_PTR(list, bb) { + printf("%s", prepend); + prepend = ", "; + printf("%p", bb); + } END_FOR_EACH_PTR(bb); + puts(""); +} + +static const char * const cap_ops[] = { + [CAP_ACQUIRE] = "acquire", + [CAP_RELEASE] = "release", + [CAP_REQUIRES] = "requires", + [CAP_GUARDED_BY] = "guarded_by", +}; + +static void show_cap(struct capability *cap) +{ + printf("cap %p %s '%s'\n", cap, + cap_ops[cap->op], + cap->expr ? show_ident(cap->expr->symbol_name) : "anon"); +} + +static void show_lock(struct lock *lock, const char *prepend, + const char *postfix) +{ + printf("%ssym %p '%s' %s", + prepend, lock->sym, + lock->sym ? show_ident(lock->sym->ident) : "anon", + postfix); +} + +static void show_lock_list(struct lock_list *locks, + const char *prepend, const char *postfix) +{ + struct lock *lock; + + FOR_EACH_PTR(locks, lock) { + show_lock(lock, prepend, postfix); + } END_FOR_EACH_PTR(lock); +} + +static void show_cap_list(struct capability_list *list, const char *name) +{ + struct capability *cap; + const char *prepend = ""; + + printf("%s:\t", name); + FOR_EACH_PTR(list, cap) { + printf("%s", prepend); + prepend = ", "; + show_cap(cap); + } END_FOR_EACH_PTR(cap); + puts(""); +} + +static void show_bb_lock_list(struct basic_block_list *list, const char *name) +{ + struct basic_block *bb; + + printf("%s:\n", name); + FOR_EACH_PTR(list, bb) { + struct bb_info *info = bb->priv; + + printf("\tbb %p\n", bb); + printf("\t\tlocks entry:\n"); + show_lock_list(info->entry, "\t\t\t", "\n"); + printf("\t\tlocks exit:\n"); + show_lock_list(info->exit, "\t\t\t", "\n"); + } END_FOR_EACH_PTR(bb); +} + +static void show_entry_lock_list(struct entrypoint *ep, int level) +{ + struct basic_block *bb = ep->entry->bb; + struct bb_info *info = bb->priv; + + printf("%*slocks entry:", level * 2, ""); + show_lock_list(info->entry, " ", ","); + printf("\n"); +} + +static void show_exit_lock_list(struct entrypoint *ep, int level) +{ + struct basic_block *bb = last_basic_block(ep->bbs); + struct bb_info *info = bb->priv; + + printf("%*slocks exit:", level * 2, ""); + show_lock_list(info->exit, " ", ","); + printf("\n"); +} + +static void show_entrypoint(struct entrypoint *ep) +{ + printf("ep:\t%s\n", ep->name->ident->name); + show_short_symbol_list(ep->name->ctype.base_type->arguments, "args"); + show_short_symbol_list(ep->syms, "syms"); + show_pseudo_list(ep->accesses, "accesses"); + show_basic_block_list(ep->bbs, "bbs"); + show_pseudo_list(ep->entry->arg_list, "arg_list"); + show_cap_list(ep->name->ctype.capabilities, "caps"); + show_bb_lock_list(ep->bbs, "locks"); +} + +static struct pseudo *lookup_accesses(struct entrypoint *ep, + struct ident *ident) +{ + struct pseudo *p; + + if (!ident) + return NULL; + + FOR_EACH_PTR(ep->accesses, p) { + if (p->ident && !strcmp(p->ident->name, ident->name)) + return p; + } END_FOR_EACH_PTR(p); + + return NULL; +} + +static struct pseudo *get_argument_pseudo(struct pseudo_list *list, int nr) +{ + struct pseudo *p; + int i = 1; + + FOR_EACH_PTR(list, p) { + if (i == nr) + return p; + i++; + } END_FOR_EACH_PTR(p); + + return NULL; +} + +static int get_argument_nr(struct symbol_list *list, struct pseudo *p) +{ + int i = 0; + struct symbol *sym; + + FOR_EACH_PTR(list, sym) { + i++; + if (strcmp(sym->ident->name, p->ident->name)) + continue; + return i; + } END_FOR_EACH_PTR(sym); + + return -1; +} + +static struct symbol *figure_access(struct pseudo *p, struct frame_list *stack) +{ + struct symbol *sym, *type; + struct frame *f; + int argc = -1; + + FOR_EACH_PTR_REVERSE(stack, f) { + if (argc >= 0) { + p = get_argument_pseudo(f->insn->arguments, argc); + if (!p) { + printf("bug bug bug bug for YOUUUUU!!\n"); + return NULL; + } + + argc = -1; + } + + if (p->type == PSEUDO_ARG) { + /* this is an argument so we can just go on + * frame up and look at the caller. + */ + argc = p->nr; + continue; + } + + if (p->type == PSEUDO_SYM) { + sym = get_base_type(p->sym); + if (is_ptr_type(sym)) { + /* so we have a pointer. was it passed + * in as argument? + */ + type = f->ep->name->ctype.base_type; + argc = get_argument_nr(type->arguments, p); + continue; + } else + return p->sym; + } + + /* p is not ARG nor SYM, that's the end of the story */ + break; + } END_FOR_EACH_PTR_REVERSE(f); + + return NULL; +} + +static struct symbol *figure_capability(struct capability *cap, + struct entrypoint *ep, + struct frame_list *stack) +{ + struct symbol *sym; + struct pseudo *p; + + if (!cap->expr) + return NULL; + + if (cap->expr->symbol) { + /* so from the linearization step we have a proper symbol, + * just get the pseudo. + */ + p = lookup_accesses(ep, cap->expr->symbol->ident); + } else { + /* no luck, we only have the name so let's use that one + * instead. + */ + p = lookup_accesses(ep, cap->expr->symbol_name); + } + + if (p) { + /* we found a pseudo in this function, let's try to + * defer it, that is where is defined. note the final + * call frame also handles the global symbols because + * they are also listed in the accesses list. + */ + sym = figure_access(p, stack); + } else { + /* the context attributes didn't get the linearize + * treatment, that means the access has not been + * added to the accesses list. first we tried + * to lookup in the accesses list but it is not there + * so we just try to see if it is a global symbol. + */ + sym = lookup_symbol(cap->expr->symbol_name, NS_SYMBOL); + } + + return sym; +} + +static void acquire_lock(struct lock_list **lset, struct entrypoint *ep, + struct frame_list *stack, struct capability *cap) +{ + struct symbol *sym; + struct lock *lock; + + sym = figure_capability(cap, ep, stack); + lock = lookup_lock(*lset, sym); + + if (!lock) { + lock = alloc_lock(sym); + add_lock(lset, lock); + } else + ref_lock(lock); +} + +static void release_lock(struct lock_list **lset, struct entrypoint *ep, + struct frame_list *stack, struct capability *cap) +{ + struct symbol *sym; + struct lock *lock; + + sym = figure_capability(cap, ep, stack); + lock = lookup_lock(*lset, sym); + + if (!lock) + return; + + if (!unref_lock(lock)) { + remove_lock(lset, lock); + __free_lock(lock); + } +} + +static void check_cap_requires(struct lock_list **lset, + struct entrypoint *ep, struct frame_list *stack) +{ + struct capability *cap; + + if (frame_list_size(stack) == 1) { + /* there is little point in checking if the caller holds + * the required locks if there is no caller. + */ + return; + } + + /* First step of validation. Let's check if we see + * the required lock in the working set. + */ + FOR_EACH_PTR(ep->name->ctype.capabilities, cap) { + struct symbol *s = figure_capability(cap, ep, stack); + struct lock *l; + + switch (cap->op) { + case CAP_REQUIRES: + l = lookup_lock(*lset, s); + if (!l) { + warning(ep->name->pos, + "function '%s' not holding '%s'", + show_ident(ep->name->ident), + s ? s->ident->name : "anon"); + } + break; + default: + break; + } + } END_FOR_EACH_PTR(cap); +} + +static void update_locks_on_entry(struct lock_list **lset, + struct entrypoint *ep, + struct frame_list *stack, + int level) +{ + struct basic_block *bb = ep->entry->bb; + struct bb_info *info = bb->priv; + + copy_lock_list(stack, *lset, &info->entry); + + check_cap_requires(lset, ep, stack); + + if (dbg_level0) + show_entry_lock_list(ep, level); +} + +static void update_locks_on_exit(struct lock_list **lset, + struct entrypoint *ep, + struct frame_list *stack, + int level) +{ + struct basic_block *bb = last_basic_block(ep->bbs); + struct bb_info *info = bb->priv; + struct capability *cap; + + FOR_EACH_PTR(ep->name->ctype.capabilities, cap) { + struct symbol *s = figure_capability(cap, ep, stack); + struct lock *l; + + switch (cap->op) { + case CAP_ACQUIRE: + acquire_lock(lset, ep, stack, cap); + break; + case CAP_RELEASE: + release_lock(lset, ep, stack, cap); + break; + case CAP_REQUIRES: + l = lookup_lock(*lset, s); + if (!l) { + warning(ep->name->pos, + "function '%s' not holding '%s'", + show_ident(ep->name->ident), + s ? s->ident->name : "anon"); + } + break; + default: + break; + } + } END_FOR_EACH_PTR(cap); + + copy_lock_list(stack, *lset, &info->exit); + + if (dbg_level0) + show_exit_lock_list(ep, level); +} + +static int function_acquires_lock(struct entrypoint *ep) +{ + struct capability *cap; + + FOR_EACH_PTR(ep->name->ctype.capabilities, cap) { + if (cap->op == CAP_ACQUIRE) + return 1; + } END_FOR_EACH_PTR(cap); + + return 0; +} + +static void check_leaking(struct entrypoint *ep) +{ + struct basic_block *bb = last_basic_block(ep->bbs); + struct bb_info *info = bb->priv; + struct lock *lock; + + /* Let's ignore function which acquire locks for the time + * beeing. + */ + if (function_acquires_lock(ep)) + return; + + FOR_EACH_PTR(info->exit, lock) { + struct stack *st; + struct frame_list *leak = NULL; + int pos; + + FOR_EACH_PTR(lock->stacks, st) { + /* Find a call stack where this ep is the first + * one. + */ + pos = stack_frame_position(st->stack, ep); + if (pos == 0) { + if (function_acquires_lock( + last_frame(st->stack)->ep)) { + leak = st->stack; + } + } else if (pos > 0) { + leak = NULL; + } + } END_FOR_EACH_PTR(st); + + if (!leak) + continue; + + warning(ep->name->pos, "leaks lock '%s'", + lock->sym ? show_ident(lock->sym->ident) : "anon"); + show_call_stack(leak, 1); + printf("\n"); + } END_FOR_EACH_PTR(lock); +} + +static void check_sym_access(struct instruction *insn, + struct symbol *sym, struct basic_block *bb, + struct lock_list *lset, + struct frame_list *stack) +{ + struct capability *c; + struct lock *l; + + FOR_EACH_PTR(sym->ctype.capabilities, c) { + struct symbol *s = figure_capability(c, bb->ep, stack); + + l = lookup_lock(lset, s); + if (!l) { + warning(insn->pos, + "accessing '%s' without holding '%s'", + sym->ident->name, + s->ident->name); + } + } END_FOR_EACH_PTR(c); +} + +static void check_bb(struct basic_block *bb, struct lock_list **lset, + struct frame_list *stack, unsigned long generation, + int level); + +static void handle_call(struct instruction *insn, struct lock_list **lset, + struct frame_list *stack, int level) +{ + struct entrypoint *ep; + struct symbol *sym; + struct frame *frame; + + if (!insn->func->ident) + return; + + sym = lookup_symbol(insn->func->ident, NS_SYMBOL); + if (!sym) + return; + ep = sym->ep; + + /* no code/entrypoint for this symbol, decleration only */ + if (!ep) + return; + + /* prevent recursions */ + frame = lookup_frame(stack, ep); + if (frame) + return; + + frame = last_frame(stack); + frame->insn = insn; + frame = alloc_frame(ep, NULL); + add_frame(&stack, frame); + + if (dbg_level0) + printf("%*scall %s\n", level * 2, "", + show_ident(ep->name->ident)); + level++; + if (dbg_level2) + show_call_stack(stack, level); + + update_locks_on_entry(lset, ep, stack, level); + check_bb(ep->entry->bb, lset, stack, ++bb_generation, level); + update_locks_on_exit(lset, ep, stack, level); + level--; + + if (dbg_level0) + printf("%*sret %s\n", level * 2, "", + show_ident(ep->name->ident)); + + frame = delete_last_frame(&stack); + __free_frame(frame); +} + +static void check_bb(struct basic_block *bb, + struct lock_list **lset, struct frame_list *stack, + unsigned long generation, int level) +{ + struct instruction *insn; + struct multijmp *mj; + struct symbol *sym; + struct bb_info *info = bb->priv; + + if (!info) { + info = __alloc_bb_info(0); + bb->priv = info; + } + + if (generation == bb->generation) + return; + bb->generation = generation; + + if (dbg_level2) + printf("%*sentry bb %p\n", level * 2, "", bb); + + FOR_EACH_PTR(bb->insns, insn) { + switch (insn->opcode) { + case OP_CALL: + handle_call(insn, lset, stack, level); + break; + case OP_BR: + if (dbg_level2) + level++; + + if (insn->bb_true) + check_bb(insn->bb_true, lset, stack, + generation, level); + if (insn->bb_false) + check_bb(insn->bb_false, lset, stack, + generation, level); + if (dbg_level2) + level--; + break; + case OP_SWITCH: + case OP_COMPUTEDGOTO: + /* Note this one might jump backwards, which means + * we need to be careful and not endup in an endless + * loop. + */ + if (dbg_level2) + level++; + FOR_EACH_PTR(insn->multijmp_list, mj) { + check_bb(mj->target, lset, stack, + generation, level); + } END_FOR_EACH_PTR(mj); + if (dbg_level2) + level--; + break; + + case OP_LOAD: + case OP_STORE: + sym = figure_access(insn->src, stack); + if (dbg_level1) + printf("%*sld/st: %p %s\n", level * 2, "", + sym, sym ? show_ident(sym->ident) : ""); + if (sym) + check_sym_access(insn, sym, bb, *lset, stack); + break; + } + } END_FOR_EACH_PTR(insn); + + if (dbg_level2) + printf("%*sexit bb %p\n", level * 2, "", bb); +} + +static void check_entrypoint(struct entrypoint *ep) +{ + struct frame_list *stack; + struct frame *frame; + struct lock_list *lset = NULL; + struct bb_info *info = ep->entry->bb->priv; + int level = 0; + + if (!info) { + info = __alloc_bb_info(0); + ep->entry->bb->priv = info; + } + + stack = NULL; + frame = alloc_frame(ep, NULL); + add_frame(&stack, frame); + + update_locks_on_entry(&lset, ep, stack, level); + check_bb(ep->entry->bb, &lset, stack, ++bb_generation, level); + update_locks_on_exit(&lset, ep, stack, level); + + frame = delete_last_frame(&stack); + __free_frame(frame); +} + +DECLARE_PTR_LIST(entrypoint_list, struct entrypoint); + +static inline void add_entrypoint(struct entrypoint_list **list, + struct entrypoint *ep) +{ + add_ptr_list(list, ep); +} + +static void check_symbols(struct symbol_list *list) +{ + struct entrypoint_list *eps = NULL; + struct entrypoint *ep; + struct symbol *sym; + + /* First pass collect all locks */ + FOR_EACH_PTR(list, sym) { + expand_symbol(sym); + ep = linearize_symbol(sym); + if (ep) { + if (dbg_level0) + printf("\n## %s()\n", + show_ident(ep->name->ident)); + + /* Call each function and collect all locks + * taken at entry and exit point of function. + */ + check_entrypoint(ep); + + add_entrypoint(&eps, ep); + } + } END_FOR_EACH_PTR(sym); + + FOR_EACH_PTR(eps, ep) { + if (dbg_level3) { + printf("\n## %s()\n", + show_ident(ep->name->ident)); + show_entrypoint(ep); + printf("\n"); + } + + check_leaking(ep); + } END_FOR_EACH_PTR(ep); +} + +int main(int argc, char **argv) +{ + struct string_list *filelist = NULL; + char *file; + + add_pre_buffer("#define __TESTLOCK__ 1\n"); + + check_symbols(sparse_initialize(argc, argv, &filelist)); + FOR_EACH_PTR_NOTAG(filelist, file) { + check_symbols(sparse(file)); + } END_FOR_EACH_PTR_NOTAG(file); + +#if 0 + show_frame_alloc(); + show_lock_alloc(); +#endif + return 0; +} diff --git a/validation/caps.c b/validation/caps.c new file mode 100644 index 0000000..0ffa407 --- /dev/null +++ b/validation/caps.c @@ -0,0 +1,80 @@ +#define __must_hold(x) __attribute__((requires_capability(x))) +#define __acquires(x) __attribute__((acquire_capability(x))) +#define __releases(x) __attribute__((release_capability(x))) +#define __guarded_by(x) __attribute__((guarded_by(x))) + +static void a(void) __acquires() +{ +} + +static void r(void) __releases() +{ +} + +static void good1(void) +{ + a(); + r(); +} + +static void okay1(void) +{ + a(); +} + +static void bad2(void) +{ + okay1(); +} + +struct hello { + char *str; + int lock; +}; + +static struct hello info __guarded_by(info.lock); + +static void wtf_lock(int *lock) + __acquires(lock) +{ + *lock = 1; +} + +static void wtf_unlock(int *lock) + __releases(lock) +{ + *lock = 0; +} + +static void set_str(struct hello *h) + __must_hold(h->lock) +{ + h->str = "hello"; +} + +static good2(void) +{ + wtf_lock(&info.lock); + set_str(&info); + wtf_unlock(&info.lock); +} + +static int global_lock; + +static good3(void) +{ + wtf_lock(&global_lock); + wtf_unlock(&global_lock); +} + +static bad4(void) +{ + wtf_lock(&global_lock); +} + +/* + * check-name: Check capabilities + * + * check-error-start + * check-error-end + */ -- 2.5.0
