diff options
| -rw-r--r-- | asm/pptok.dat | 1 | ||||
| -rw-r--r-- | asm/preproc.c | 87 | ||||
| -rw-r--r-- | include/rbtree.h | 49 | ||||
| -rw-r--r-- | nasmlib/rbtree.c | 212 | ||||
| -rw-r--r-- | output/outlib.c | 278 | ||||
| -rw-r--r-- | output/outlib.h | 252 | ||||
| -rw-r--r-- | test/require.asm | 2 | ||||
| -rw-r--r-- | version | 2 |
8 files changed, 800 insertions, 83 deletions
diff --git a/asm/pptok.dat b/asm/pptok.dat index b6285c36..9b890a19 100644 --- a/asm/pptok.dat +++ b/asm/pptok.dat @@ -94,6 +94,7 @@ %push %rep %repl +%require %rotate %stacksize %undef diff --git a/asm/preproc.c b/asm/preproc.c index aded0bec..116ceef6 100644 --- a/asm/preproc.c +++ b/asm/preproc.c @@ -2205,10 +2205,11 @@ static Context *get_ctx(const char *name, const char **namep) * the end of the path. * * Note: for INC_PROBE the function returns NULL at all times; - * instead look for the + * instead look for a filename in *slpath. */ enum incopen_mode { INC_NEEDED, /* File must exist */ + INC_REQUIRED, /* File must exist, but only open once/pass */ INC_OPTIONAL, /* Missing is OK */ INC_PROBE /* Only an existence probe */ }; @@ -2253,41 +2254,88 @@ static FILE *inc_fopen_search(const char *file, char **slpath, * Open a file, or test for the presence of one (depending on omode), * considering the include path. */ +struct file_hash_entry { + const char *path; + struct file_hash_entry *full; /* Hash entry for the full path */ + int64_t include_pass; /* Pass in which last included (for %require) */ +}; + static FILE *inc_fopen(const char *file, struct strlist *dhead, const char **found_path, enum incopen_mode omode, enum file_flags fmode) { + struct file_hash_entry **fhep; + struct file_hash_entry *fhe = NULL; struct hash_insert hi; - void **hp; - char *path; + const char *path = NULL; FILE *fp = NULL; - - hp = hash_find(&FileHash, file, &hi); - if (hp) { - path = *hp; - if (path || omode != INC_NEEDED) { - strlist_add(dhead, path ? path : file); + const int64_t pass = pass_count(); + bool skip_open = (omode == INC_PROBE); + + fhep = (struct file_hash_entry **)hash_find(&FileHash, file, &hi); + if (fhep) { + fhe = *fhep; + if (fhe) { + path = fhe->path; + skip_open |= (omode == INC_REQUIRED) && + (fhe->full->include_pass >= pass); } } else { /* Need to do the actual path search */ - fp = inc_fopen_search(file, &path, omode, fmode); + char *pptr; + fp = inc_fopen_search(file, &pptr, omode, fmode); + path = pptr; /* Positive or negative result */ - hash_add(&hi, nasm_strdup(file), path); + if (path) { + nasm_new(fhe); + fhe->path = path; + fhe->full = fhe; /* It is *possible*... */ + } + hash_add(&hi, nasm_strdup(file), fhe); + + /* + * Add a hash entry for the canonical path if there isn't one + * already. Try to get the unique name from the OS best we can. + * Note that ->path and ->full->path can be different, and that + * is okay (we don't want to print out a full canonical path + * in messages, for example.) + */ + if (path) { + char *fullpath = nasm_realpath(path); + + if (!strcmp(file, fullpath)) { + nasm_free(fullpath); + } else { + struct file_hash_entry **fullp, *full; + fullp = (struct file_hash_entry **) + hash_find(&FileHash, fullpath, &hi); + + if (fullp) { + full = *fullp; + nasm_free(fullpath); + } else { + nasm_new(full); + full->path = fullpath; + full->full = full; + hash_add(&hi, path, full); + } + fhe->full = full; + } + } /* * Add file to dependency path. */ - if (path || omode != INC_NEEDED) - strlist_add(dhead, file); + strlist_add(dhead, path ? path : file); } if (path && !fp && omode != INC_PROBE) fp = nasm_open_read(path, fmode); - if (omode == INC_NEEDED && !fp) { + if (omode < INC_OPTIONAL && !fp) { if (!path) errno = ENOENT; @@ -2295,6 +2343,9 @@ static FILE *inc_fopen(const char *file, file, strerror(errno)); } + if (fp) + fhe->full->include_pass = pass; + if (found_path) *found_path = path; @@ -3777,6 +3828,7 @@ static int do_directive(Token *tline, Token **output) goto done; case PP_INCLUDE: + case PP_REQUIRE: t = tline->next = expand_smacro(tline->next); t = skip_white(t); @@ -3792,10 +3844,11 @@ static int do_directive(Token *tline, Token **output) inc->next = istk; found_path = NULL; inc->fp = inc_fopen(p, deplist, &found_path, - (pp_mode == PP_DEPS) - ? INC_OPTIONAL : INC_NEEDED, NF_TEXT); + (pp_mode == PP_DEPS) ? INC_OPTIONAL : + (op == PP_REQUIRE) ? INC_REQUIRED : + INC_NEEDED, NF_TEXT); if (!inc->fp) { - /* -MG given but file not found */ + /* -MG given but file not found, or repeated %require */ nasm_free(inc); } else { src_set(0, found_path ? found_path : p); diff --git a/include/rbtree.h b/include/rbtree.h index f0ffb914..8ccd129c 100644 --- a/include/rbtree.h +++ b/include/rbtree.h @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------- * - * - * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * + * Copyright 1996-2020 The NASM Authors - All Rights Reserved * See the file AUTHORS included with the NASM distribution for * the specific copyright holders. * @@ -14,7 +14,7 @@ * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. - * + * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF @@ -36,16 +36,47 @@ #include "compiler.h" -/* This structure should be embedded in a larger data structure; - the final output from rb_search() can then be converted back - to the larger data structure via container_of(). */ +/* + * This structure should be embedded in a larger data structure; + * the final output from rb_search() can then be converted back + * to the larger data structure via container_of(). + * + * An empty tree is simply represented by a NULL pointer. + */ + +/* Note: the values of these flags is significant */ +enum rbtree_node_flags { + RBTREE_NODE_BLACK = 1, /* Node color is black */ + RBTREE_NODE_PRED = 2, /* Left pointer is an uplink */ + RBTREE_NODE_SUCC = 4 /* Right pointer is an uplink */ +}; + struct rbtree { uint64_t key; - struct rbtree *left, *right; - bool red; + struct rbtree_metadata { + struct rbtree *left, *right; + enum rbtree_node_flags flags; + } m; }; +/* + * Add a node to a tree. Returns the new root pointer. + * The key value in the structure needs to be preinitialized; + * the rest of the structure should be zero. + */ struct rbtree *rb_insert(struct rbtree *, struct rbtree *); -struct rbtree *rb_search(struct rbtree *, uint64_t); + +/* + * Find a node in the tree corresponding to the key immediately + * <= the passed-in key value. + */ +struct rbtree *rb_search(const struct rbtree *, uint64_t); + +/* + * Return the immediately previous or next node in key order. + * Returns NULL if this node is the end of the + */ +struct rbtree *rb_prev(const struct rbtree *); +struct rbtree *rb_next(const struct rbtree *); #endif /* NASM_RBTREE_H */ diff --git a/nasmlib/rbtree.c b/nasmlib/rbtree.c index 5af6067d..8b74c0c4 100644 --- a/nasmlib/rbtree.c +++ b/nasmlib/rbtree.c @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------- * - * - * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * + * Copyright 1996-2020 The NASM Authors - All Rights Reserved * See the file AUTHORS included with the NASM distribution for * the specific copyright holders. * @@ -14,7 +14,7 @@ * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. - * + * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF @@ -34,86 +34,202 @@ /* * rbtree.c * - * Simple implementation of a left-leaning red-black tree with 64-bit - * integer keys. The search operation will return the highest node <= - * the key; only search and insert are supported, but additional - * standard llrbtree operations can be coded up at will. + * Simple implementation of a "left-leaning threaded red-black tree" + * with 64-bit integer keys. The search operation will return the + * highest node <= the key; only search and insert are supported, but + * additional standard llrbtree operations can be coded up at will. * * See http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf for * information about left-leaning red-black trees. + * + * The "threaded" part means that left and right pointers that would + * otherwise be NULL are pointers to the in-order predecessor or + * successor node. The only pointers that are NULL are the very left- + * and rightmost, for which no corresponding side node exists. + * + * This, among other things, allows for efficient predecessor and + * successor operations without requiring dedicated space for a parent + * pointer. + * + * This implementation is robust for identical key values; such keys + * will not have their insertion order preserved, and after insertion + * of unrelated keys a lookup may return a different node for the + * duplicated key, but the prev/next operations will always enumerate + * all entries. + * + * The NULL pointers at the end are considered predecessor/successor + * pointers, so if the corresponding flags are clear it is always safe + * to access the pointed-to object without an explicit NULL pointer + * check. */ #include "rbtree.h" +#include "nasmlib.h" -struct rbtree *rb_search(struct rbtree *tree, uint64_t key) +struct rbtree *rb_search(const struct rbtree *tree, uint64_t key) { - struct rbtree *best = NULL; - - while (tree) { - if (tree->key == key) - return tree; - else if (tree->key > key) - tree = tree->left; - else { - best = tree; - tree = tree->right; + const struct rbtree *best = NULL; + + if (tree) { + while (true) { + if (tree->key > key) { + if (tree->m.flags & RBTREE_NODE_PRED) + break; + tree = tree->m.left; + } else { + best = tree; + if (tree->key == key || (tree->m.flags & RBTREE_NODE_SUCC)) + break; + tree = tree->m.right; + } } } - return best; + return (struct rbtree *)best; +} + +/* Reds two left in a row? */ +static inline bool is_red_left_left(struct rbtree *h) +{ + return !(h->m.flags & RBTREE_NODE_PRED) && + !(h->m.left->m.flags & (RBTREE_NODE_BLACK|RBTREE_NODE_PRED)) && + !(h->m.left->m.left->m.flags & RBTREE_NODE_BLACK); } -static bool is_red(struct rbtree *h) +/* Node to the right is red? */ +static inline bool is_red_right(struct rbtree *h) { - return h && h->red; + return !(h->m.flags & RBTREE_NODE_SUCC) && + !(h->m.right->m.flags & RBTREE_NODE_BLACK); } -static struct rbtree *rotate_left(struct rbtree *h) +/* Both the left and right hand nodes are red? */ +static inline bool is_red_both(struct rbtree *h) { - struct rbtree *x = h->right; - h->right = x->left; - x->left = h; - x->red = x->left->red; - x->left->red = true; + return !(h->m.flags & (RBTREE_NODE_PRED|RBTREE_NODE_SUCC)) + && !(h->m.left->m.flags & h->m.right->m.flags & RBTREE_NODE_BLACK); +} + +static inline struct rbtree *rotate_left(struct rbtree *h) +{ + struct rbtree *x = h->m.right; + enum rbtree_node_flags hf = h->m.flags; + enum rbtree_node_flags xf = x->m.flags; + + if (xf & RBTREE_NODE_PRED) { + h->m.right = x; + h->m.flags = (hf & RBTREE_NODE_PRED) | RBTREE_NODE_SUCC; + } else { + h->m.right = x->m.left; + h->m.flags = hf & RBTREE_NODE_PRED; + } + x->m.flags = (hf & RBTREE_NODE_BLACK) | (xf & RBTREE_NODE_SUCC); + x->m.left = h; + return x; } -static struct rbtree *rotate_right(struct rbtree *h) +static inline struct rbtree *rotate_right(struct rbtree *h) { - struct rbtree *x = h->left; - h->left = x->right; - x->right = h; - x->red = x->right->red; - x->right->red = true; + struct rbtree *x = h->m.left; + enum rbtree_node_flags hf = h->m.flags; + enum rbtree_node_flags xf = x->m.flags; + + if (xf & RBTREE_NODE_SUCC) { + h->m.left = x; + h->m.flags = (hf & RBTREE_NODE_SUCC) | RBTREE_NODE_PRED; + } else { + h->m.left = x->m.right; + h->m.flags = hf & RBTREE_NODE_SUCC; + } + x->m.flags = (hf & RBTREE_NODE_BLACK) | (xf & RBTREE_NODE_PRED); + x->m.right = h; + return x; } -static void color_flip(struct rbtree *h) +static inline void color_flip(struct rbtree *h) { - h->red = !h->red; - h->left->red = !h->left->red; - h->right->red = !h->right->red; + h->m.flags ^= RBTREE_NODE_BLACK; + h->m.left->m.flags ^= RBTREE_NODE_BLACK; + h->m.right->m.flags ^= RBTREE_NODE_BLACK; } +static struct rbtree * +_rb_insert(struct rbtree *tree, struct rbtree *node); + struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node) { - if (!tree) { - node->red = true; - return node; - } + /* Initialize node as if it was the sole member of the tree */ + + nasm_zero(node->m); + node->m.flags = RBTREE_NODE_PRED|RBTREE_NODE_SUCC; + + if (unlikely(!tree)) + return node; + + return _rb_insert(tree, node); +} - if (is_red(tree->left) && is_red(tree->right)) +static struct rbtree * +_rb_insert(struct rbtree *tree, struct rbtree *node) +{ + /* Recursive part of the algorithm */ + + /* Red on both sides? */ + if (is_red_both(tree)) color_flip(tree); - if (node->key < tree->key) - tree->left = rb_insert(tree->left, node); - else - tree->right = rb_insert(tree->right, node); + if (node->key < tree->key) { + node->m.right = tree; /* Potential successor */ + if (tree->m.flags & RBTREE_NODE_PRED) { + node->m.left = tree->m.left; + tree->m.flags &= ~RBTREE_NODE_PRED; + tree->m.left = node; + } else { + tree->m.left = _rb_insert(tree->m.left, node); + } + } else { + node->m.left = tree; /* Potential predecessor */ + if (tree->m.flags & RBTREE_NODE_SUCC) { + node->m.right = tree->m.right; + tree->m.flags &= ~RBTREE_NODE_SUCC; + tree->m.right = node; + } else { + tree->m.right = _rb_insert(tree->m.right, node); + } + } - if (is_red(tree->right)) + if (is_red_right(tree)) tree = rotate_left(tree); - if (is_red(tree->left) && is_red(tree->left->left)) + if (is_red_left_left(tree)) tree = rotate_right(tree); return tree; } + +struct rbtree *rb_prev(const struct rbtree *node) +{ + struct rbtree *np = node->m.left; + + if (node->m.flags & RBTREE_NODE_PRED) + return np; + + while (!(np->m.flags & RBTREE_NODE_SUCC)) + np = np->m.right; + + return np; +} + +struct rbtree *rb_next(const struct rbtree *node) +{ + struct rbtree *np = node->m.right; + + if (node->m.flags & RBTREE_NODE_SUCC) + return np; + + while (!(np->m.flags & RBTREE_NODE_PRED)) + np = np->m.left; + + return np; +} diff --git a/output/outlib.c b/output/outlib.c index c60de055..fa7db15e 100644 --- a/output/outlib.c +++ b/output/outlib.c @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------- * - * - * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * + * Copyright 1996-2020 The NASM Authors - All Rights Reserved * See the file AUTHORS included with the NASM distribution for * the specific copyright holders. * @@ -14,7 +14,7 @@ * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. - * + * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF @@ -32,14 +32,13 @@ * ----------------------------------------------------------------------- */ /* - * libout.c + * outlib.c * * Common routines for the output backends. */ -#include "compiler.h" -#include "nasm.h" #include "outlib.h" +#include "raa.h" uint64_t realsize(enum out_type type, uint64_t size) { @@ -56,3 +55,270 @@ uint64_t realsize(enum out_type type, uint64_t size) return size; } } + +/* Common section/symbol handling */ + +struct ol_sect *_ol_sect_list; +uint64_t _ol_nsects; /* True sections, not external symbols */ +static struct ol_sect **ol_sect_tail = &_ol_sect_list; +static struct hash_table ol_secthash; +static struct RAA *ol_sect_index_tbl; + +struct ol_sym *_ol_sym_list; +uint64_t _ol_nsyms; +static struct ol_sym **ol_sym_tail = &_ol_sym_list; +static struct hash_table ol_symhash; + +void ol_init(void) +{ +} + +static void ol_free_symbols(void) +{ + struct ol_sym *s, *stmp; + + hash_free(&ol_symhash); + + list_for_each_safe(s, stmp, _ol_sym_list) { + nasm_free((char *)s->name); + nasm_free(s); + } + + _ol_nsyms = 0; + _ol_sym_list = NULL; + ol_sym_tail = &_ol_sym_list; +} + +static void ol_free_sections(void) +{ + struct ol_sect *s, *stmp; + + hash_free(&ol_secthash); + raa_free(ol_sect_index_tbl); + ol_sect_index_tbl = NULL; + + list_for_each_safe(s, stmp, _ol_sect_list) { + saa_free(s->data); + saa_free(s->reloc); + nasm_free((char *)s->name); + nasm_free(s); + } + + _ol_nsects = 0; + _ol_sect_list = NULL; + ol_sect_tail = &_ol_sect_list; +} + +void ol_cleanup(void) +{ + ol_free_symbols(); + ol_free_sections(); +} + +/* + * Allocate a section index and add a section, subsection, or external + * symbol to the section-by-index table. If the index provided is zero, + * allocate a new index via seg_alloc(). + */ +static uint32_t ol_seg_alloc(void *s, uint32_t ix) +{ + if (!ix) + ix = seg_alloc(); + ol_sect_index_tbl = raa_write_ptr(ol_sect_index_tbl, ix >> 1, s); + return ix; +} + +/* + * Find a section or create a new section structure if it does not exist + * and allocate it an index value via seg_alloc(). + */ +struct ol_sect *_ol_get_sect(const char *name, size_t ssize, size_t rsize) +{ + struct ol_sect *s, **sp; + struct hash_insert hi; + + sp = (struct ol_sect **)hash_find(&ol_secthash, name, &hi); + if (sp) + return *sp; + + s = nasm_zalloc(ssize); + s->syml.tail = &s->syml.head; + s->name = nasm_strdup(name); + s->data = saa_init(1); + s->reloc = saa_init(rsize); + *ol_sect_tail = s; + ol_sect_tail = &s->next; + _ol_nsects++; + s->index = s->subindex = ol_seg_alloc(s, 0); + + hash_add(&hi, s->name, s); + return s; +} + +/* Find a section by name without creating one */ +struct ol_sect *_ol_sect_by_name(const char *name) +{ + struct ol_sect **sp; + + sp = (struct ol_sect **)hash_find(&ol_secthash, name, NULL); + return sp ? *sp : NULL; +} + +/* Find a section or external symbol by index; NULL if not valid */ +struct ol_sect *_ol_sect_by_index(int32_t index) +{ + uint32_t ix = index; + + if (unlikely(ix >= SEG_ABS)) + return NULL; + + return raa_read_ptr(ol_sect_index_tbl, ix >> 1); +} + +/* + * Start a new subsection for the given section. At the moment, once a + * subsection has been created, it is not possible to revert to an + * earlier subsection. ol_sect_by_index() will return the main section + * structure. Returns the new section index. This is used to prevent + * the front end from optimizing across subsection boundaries. + */ +int32_t _ol_new_subsection(struct ol_sect *sect) +{ + if (unlikely(!sect)) + return NO_SEG; + + return sect->subindex = ol_seg_alloc(sect, 0); +} + +/* + * Insert a symbol into a list; need to use upcasting using container_of() + * to walk the list later. + */ +void ol_add_sym_to(struct ol_symlist *syml, struct ol_symhead *head, + uint64_t offset) +{ + syml->tree.key = offset; + head->tree = rb_insert(head->tree, &syml->tree); + *head->tail = syml; + head->tail = &syml->next; + head->n++; +} + +/* + * Create a location structure from seg:offs + */ +void ol_mkloc(struct ol_loc *loc, int64_t offs, int32_t seg) +{ + nasm_zero(*loc); + loc->offs = offs; + + if (unlikely((uint32_t)seg >= SEG_ABS)) { + if (likely(seg == NO_SEG)) { + loc->seg.t = OS_NOSEG; + } else { + loc->seg.t = OS_ABS; + loc->seg.index = seg - SEG_ABS; + } + } else { + loc->seg.index = seg & ~1; + loc->seg.t = OS_SECT | (seg & 1); + loc->seg.s.sect = _ol_sect_by_index(loc->seg.index); + } +} + +/* + * Create a new symbol. If this symbol is OS_OFFS, add it to the relevant + * section, too. If the symbol already exists, return NULL; this is + * different from ol_get_section() as a single section may be invoked + * many times. On the contrary, the front end will prevent a single symbol + * from being defined more than once. + * + * If flags has OF_GLOBAL set, add it to the global symbol hash for + * the containing section if applicable. + * + * If flags has OF_IMPSEC set, allocate a segment index for it via + * seg_alloc() unless v->index is already set, and add it to the + * section by index list. + */ +struct ol_sym *_ol_new_sym(const char *name, const struct ol_loc *v, + uint32_t flags, size_t size) +{ + struct hash_insert hi; + struct ol_sym *sym; + + if (hash_find(&ol_symhash, name, &hi)) + return NULL; /* Symbol already exists */ + + flags |= OF_SYMBOL; + + sym = nasm_zalloc(size); + sym->name = nasm_strdup(name); + sym->v = *v; + + if (sym->v.seg.t & OS_SECT) { + struct ol_sect *sect = sym->v.seg.s.sect; + + if (!sect || (sect->flags & OF_SYMBOL)) + /* Must be an external or common reference */ + flags |= OF_IMPSEC; + + if (flags & OF_IMPSEC) { + /* Metasection */ + if (!sym->v.seg.s.sym) { + sym->v.seg.s.sym = sym; + sym->v.seg.index = ol_seg_alloc(sym, sym->v.seg.index); + } + } else if (sym->v.seg.t == OS_OFFS) { + struct ol_sect * const sect = sym->v.seg.s.sect; + const uint64_t offs = sym->v.offs; + + ol_add_sym_to(&sym->syml, §->syml, offs); + if (flags & OF_GLOBAL) + ol_add_sym_to(&sym->symg, §->symg, offs); + } + } + sym->flags = flags; + + *ol_sym_tail = sym; + ol_sym_tail = &sym->next; + _ol_nsyms++; + + hash_add(&hi, sym->name, sym); + return sym; +} + +/* Find a symbol in the global namespace */ +struct ol_sym *_ol_sym_by_name(const char *name) +{ + struct ol_sym **symp; + + symp = (struct ol_sym **)hash_find(&ol_symhash, name, NULL); + return symp ? *symp : NULL; +} + +/* + * Find a symbol by address in a specific section. If no symbol is defined + * at that exact address, return the immediately previously defined one. + * If global is set, then only return global symbols. + */ +struct ol_sym *_ol_sym_by_address(struct ol_sect *sect, int64_t addr, + bool global) +{ + struct ol_symhead *head; + size_t t_offs; + struct rbtree *t; + + if (global) { + head = §->symg; + t_offs = offsetof(struct ol_sym, symg.tree); + } else { + head = §->syml; + t_offs = offsetof(struct ol_sym, syml.tree); + } + + t = rb_search(head->tree, addr); + if (!t) + return NULL; + + return (struct ol_sym *)((char *)t - t_offs); +} diff --git a/output/outlib.h b/output/outlib.h index 30f2c0b2..a0b31245 100644 --- a/output/outlib.h +++ b/output/outlib.h @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------- * * - * Copyright 1996-2018 The NASM Authors - All Rights Reserved + * Copyright 1996-2020 The NASM Authors - All Rights Reserved * See the file AUTHORS included with the NASM distribution for * the specific copyright holders. * @@ -34,8 +34,12 @@ #ifndef NASM_OUTLIB_H #define NASM_OUTLIB_H +#include "compiler.h" #include "nasm.h" #include "error.h" +#include "hashtbl.h" +#include "saa.h" +#include "rbtree.h" uint64_t realsize(enum out_type type, uint64_t size); @@ -61,5 +65,249 @@ extern const struct dfmt * const null_debug_arr[2]; /* Wrapper for unported backends */ void nasm_do_legacy_output(const struct out_data *data); -#endif /* NASM_OUTLIB_H */ +/* + * Common routines for tasks that really should migrate into the core. + * This provides a common interface for maintaining sections and symbols, + * and provide quick lookups as well as declared-order sequential walks. + * + * These structures are intended to be embedded at the *top* of a + * backend-specific structure containing additional information. + * + * The tokens O_Section, O_Symbol and O_Reloc are intended to be + * defined as macros by the backend before including this file! + */ + +struct ol_sect; +struct ol_sym; + +#ifndef O_Section +typedef struct ol_sect O_Section; +#endif +#ifndef O_Symbol +typedef struct ol_sym O_Symbol; +#endif +#ifndef O_Reloc +typedef void * O_Reloc; +#endif + +/* Common section structure */ + +/* + * Common flags for sections and symbols; low values reserved for + * backend. Note that both ol_sect and ol_sym begin with a flags + * field, so if a section pointer points to an external symbol instead + * they can be trivially resolved. + */ +#define OF_SYMBOL 0x80000000 +#define OF_GLOBAL 0x40000000 +#define OF_IMPSEC 0x20000000 +#define OF_COMMON 0x10000000 + +struct ol_sym; + +struct ol_symlist { + struct ol_symlist *next; + struct rbtree tree; +}; +struct ol_symhead { + struct ol_symlist *head, **tail; + struct rbtree *tree; + uint64_t n; +}; + +struct ol_sect { + uint32_t flags; /* Section/symbol flags */ + struct ol_sect *next; /* Next section in declared order */ + const char *name; /* Name of section */ + struct ol_symhead syml; /* All symbols in this section */ + struct ol_symhead symg; /* Global symbols in this section */ + struct SAA *data; /* Contents of section */ + struct SAA *reloc; /* Section relocations */ + uint32_t index; /* Primary section index */ + uint32_t subindex; /* Current subsection index */ +}; + +/* Segment reference */ +enum ol_seg_type { + OS_NOSEG = 0, /* Plain number (no segment) */ + OS_SEGREF = 1, /* It is a segment reference */ + OS_ABS = 1, /* Absolute segment reference */ + OS_SECT = 2, /* It is a real section */ + OS_OFFS = OS_SECT, /* Offset reference in section */ + OS_SEG = OS_SECT|OS_SEGREF /* Section reference */ +}; + +union ol_segval { + struct ol_sect *sect; /* Section structure */ + struct ol_sym *sym; /* External symbol structure */ +}; + +struct ol_seg { + union ol_segval s; + enum ol_seg_type t; + + /* + * For a section: subsection index + * For a metasymbol: virtual segment index + * For an absolute symbol: absolute value + */ + uint32_t index; +}; + +/* seg:offs representing the full location value and type */ +struct ol_loc { + int64_t offs; + struct ol_seg seg; +}; + +/* Common symbol structure */ +struct ol_sym { + uint32_t flags; /* Section/symbol flags */ + uint32_t size; /* Size value (for backend) */ + struct ol_sym *next; /* Next symbol in declared order */ + const char *name; /* Symbol name */ + struct ol_symlist syml; /* Section-local symbol list */ + struct ol_symlist symg; /* Section-local global symbol list */ + struct ol_loc p; /* Symbol position ("where") */ + struct ol_loc v; /* Symbol value ("what") */ +}; + +/* + * Operations + */ +void ol_init(void); +void ol_cleanup(void); +/* Convert offs:seg to a location structure */ +extern void +ol_mkloc(struct ol_loc *loc, int64_t offs, int32_t seg); + +/* Get the section or external symbol from a struct ol_seg */ +static inline O_Section *seg_sect(struct ol_seg *seg) +{ + return (O_Section *)seg->s.sect; +} +static inline O_Symbol *seg_xsym(struct ol_seg *seg) +{ + return (O_Symbol *)seg->s.sym; +} + +/* + * Return a pointer to the symbol structure if and only if a section is + * really a symbol of some kind (extern, common...) + */ +static inline struct ol_sym *_seg_extsym(struct ol_sect *sect) +{ + return (sect->flags & OF_SYMBOL) ? (struct ol_sym *)sect : NULL; +} +static inline O_Symbol *seg_extsym(O_Section *sect) +{ + return (O_Symbol *)_seg_extsym((struct ol_sect *)sect); +} + +/* + * Find a section or create a new section structure if it does not exist + * and allocate it an index value via seg_alloc(). + */ +extern struct ol_sect * +_ol_get_sect(const char *name, size_t ssize, size_t rsize); +static inline O_Section *ol_get_sect(const char *name) +{ + return (O_Section *)_ol_get_sect(name, sizeof(O_Section), sizeof(O_Reloc)); +} + +/* Find a section by name without creating one */ +extern struct ol_sect *_ol_sect_by_name(const char *); +static inline O_Section *ol_sect_by_name(const char *name) +{ + return (O_Section *)_ol_sect_by_name(name); +} + +/* Find a section or external symbol by index; NULL if not valid */ +extern struct ol_sect *_ol_sect_by_index(int32_t index); +static inline O_Section *ol_sect_by_index(int32_t index) +{ + return (O_Section *)_ol_sect_by_index(index); +} + +/* Global list of sections (not including external symbols) */ +extern struct ol_sect *_ol_sect_list; +static inline O_Section *ol_sect_list(void) +{ + return (O_Section *)_ol_sect_list; +} + +/* Count of sections (not including external symbols) */ +extern uint64_t _ol_nsects; +static inline uint64_t ol_nsects(void) +{ + return _ol_nsects; +} + +/* + * Start a new subsection for the given section. At the moment, once a + * subsection has been created, it is not possible to revert to an + * earlier subsection. ol_sect_by_index() will return the main section + * structure. Returns the new section index. This is used to prevent + * the front end from optimizing across subsection boundaries. + */ +extern int32_t _ol_new_subsection(struct ol_sect *sect); +static inline int32_t ol_new_subsection(O_Section *sect) +{ + return ol_new_subsection((struct ol_sect *)sect); +} + +/* + * Create a new symbol. If this symbol is OS_OFFS, add it to the relevant + * section, too. If the symbol already exists, return NULL; this is + * different from ol_get_section() as a single section may be invoked + * many times. On the contrary, the front end will prevent a single symbol + * from being defined more than once. + * + * If flags has OF_GLOBAL set, add it to the global symbol hash for the + * containing section. If flags has OF_IMPSEC set, allocate a segment + * index for it via seg_alloc() and add it to the section by index list. + */ +extern struct ol_sym *_ol_new_sym(const char *name, const struct ol_loc *v, + uint32_t flags, size_t size); +static inline O_Symbol *ol_new_sym(const char *name, const struct ol_loc *v, + uint32_t flags) +{ + return (O_Symbol *)_ol_new_sym(name, v, flags, sizeof(O_Symbol)); +} + +/* Find a symbol by name in the global namespace */ +extern struct ol_sym *_ol_sym_by_name(const char *name); +static inline O_Symbol *ol_sym_by_name(const char *name) +{ + return (O_Symbol *)_ol_sym_by_name(name); +} + +/* + * Find a symbol by address in a specific section. If no symbol is defined + * at that exact address, return the immediately previously defined one. + * If global is set, then only return global symbols. + */ +extern struct ol_sym *_ol_sym_by_address(struct ol_sect *sect, int64_t addr, + bool global); +static inline O_Symbol *ol_sym_by_address(O_Section *sect, int64_t addr, + bool global) +{ + return (O_Symbol *)_ol_sym_by_address((struct ol_sect *)sect, addr, global); +} + +/* Global list of symbols */ +extern struct ol_sym *_ol_sym_list; +static inline O_Symbol *ol_sym_list(void) +{ + return (O_Symbol *)_ol_sym_list; +} + +/* Global count of symbols */ +extern uint64_t _ol_nsyms; +static inline uint64_t ol_nsyms(void) +{ + return _ol_nsyms; +} + +#endif /* NASM_OUTLIB_H */ diff --git a/test/require.asm b/test/require.asm new file mode 100644 index 00000000..169c5638 --- /dev/null +++ b/test/require.asm @@ -0,0 +1,2 @@ +%require 'require.asm' + db 1 @@ -1 +1 @@ -2.15.02 +2.16rc0 |