output/outlib.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2020 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 /*
  35  * outlib.c
  36  *
  37  * Common routines for the output backends.
  38  */
  39
  40 #include "outlib.h"
  41 #include "raa.h"
  42
  43 uint64_t realsize(enum out_type type, uint64_t size)
  44 {
  45     switch (type) {
  46     case OUT_REL1ADR:
  47         return 1;
  48     case OUT_REL2ADR:
  49         return 2;
  50     case OUT_REL4ADR:
  51         return 4;
  52     case OUT_REL8ADR:
  53         return 8;
  54     default:
  55         return size;
  56     }
  57 }
  58
  59 /* Common section/symbol handling */
  60
  61 struct ol_sect *_ol_sect_list;
  62 uint64_t _ol_nsects;             /* True sections, not external symbols */
  63 static struct ol_sect **ol_sect_tail = &_ol_sect_list;
  64 static struct hash_table ol_secthash;
  65 static struct RAA *ol_sect_index_tbl;
  66
  67 struct ol_sym *_ol_sym_list;
  68 uint64_t _ol_nsyms;
  69 static struct ol_sym **ol_sym_tail = &_ol_sym_list;
  70 static struct hash_table ol_symhash;
  71
  72 void ol_init(void)
  73 {
  74 }
  75
  76 static void ol_free_symbols(void)
  77 {
  78     struct ol_sym *s, *stmp;
  79
  80     hash_free(&ol_symhash);
  81
  82     list_for_each_safe(s, stmp, _ol_sym_list) {
  83         nasm_free((char *)s->name);
  84         nasm_free(s);
  85     }
  86
  87     _ol_nsyms = 0;
  88     _ol_sym_list = NULL;
  89     ol_sym_tail = &_ol_sym_list;
  90 }
  91
  92 static void ol_free_sections(void)
  93 {
  94     struct ol_sect *s, *stmp;
  95
  96     hash_free(&ol_secthash);
  97     raa_free(ol_sect_index_tbl);
  98     ol_sect_index_tbl = NULL;
  99
 100     list_for_each_safe(s, stmp, _ol_sect_list) {
 101         saa_free(s->data);
 102         saa_free(s->reloc);
 103         nasm_free((char *)s->name);
 104         nasm_free(s);
 105     }
 106
 107     _ol_nsects = 0;
 108     _ol_sect_list = NULL;
 109     ol_sect_tail = &_ol_sect_list;
 110 }
 111
 112 void ol_cleanup(void)
 113 {
 114     ol_free_symbols();
 115     ol_free_sections();
 116 }
 117
 118 /*
 119  * Allocate a section index and add a section, subsection, or external
 120  * symbol to the section-by-index table. If the index provided is zero,
 121  * allocate a new index via seg_alloc().
 122  */
 123 static uint32_t ol_seg_alloc(void *s, uint32_t ix)
 124 {
 125     if (!ix)
 126         ix = seg_alloc();
 127     ol_sect_index_tbl = raa_write_ptr(ol_sect_index_tbl, ix >> 1, s);
 128     return ix;
 129 }
 130
 131 /*
 132  * Find a section or create a new section structure if it does not exist
 133  * and allocate it an index value via seg_alloc().
 134  */
 135 struct ol_sect *_ol_get_sect(const char *name, size_t ssize, size_t rsize)
 136 {
 137     struct ol_sect *s, **sp;
 138     struct hash_insert hi;
 139
 140     sp = (struct ol_sect **)hash_find(&ol_secthash, name, &hi);
 141     if (sp)
 142         return *sp;
 143
 144     s             = nasm_zalloc(ssize);
 145     s->syml.tail  = &s->syml.head;
 146     s->name       = nasm_strdup(name);
 147     s->data       = saa_init(1);
 148     s->reloc      = saa_init(rsize);
 149     *ol_sect_tail = s;
 150     ol_sect_tail  = &s->next;
 151     _ol_nsects++;
 152     s->index     = s->subindex = ol_seg_alloc(s, 0);
 153
 154     hash_add(&hi, s->name, s);
 155     return s;
 156 }
 157
 158 /* Find a section by name without creating one */
 159 struct ol_sect *_ol_sect_by_name(const char *name)
 160 {
 161     struct ol_sect **sp;
 162
 163     sp = (struct ol_sect **)hash_find(&ol_secthash, name, NULL);
 164     return sp ? *sp : NULL;
 165 }
 166
 167 /* Find a section or external symbol by index; NULL if not valid */
 168 struct ol_sect *_ol_sect_by_index(int32_t index)
 169 {
 170     uint32_t ix = index;
 171
 172     if (unlikely(ix >= SEG_ABS))
 173         return NULL;
 174
 175     return raa_read_ptr(ol_sect_index_tbl, ix >> 1);
 176 }
 177
 178 /*
 179  * Start a new subsection for the given section. At the moment, once a
 180  * subsection has been created, it is not possible to revert to an
 181  * earlier subsection. ol_sect_by_index() will return the main section
 182  * structure. Returns the new section index.  This is used to prevent
 183  * the front end from optimizing across subsection boundaries.
 184  */
 185 int32_t _ol_new_subsection(struct ol_sect *sect)
 186 {
 187     if (unlikely(!sect))
 188         return NO_SEG;
 189
 190     return sect->subindex = ol_seg_alloc(sect, 0);
 191 }
 192
 193 /*
 194  * Insert a symbol into a list; need to use upcasting using container_of()
 195  * to walk the list later.
 196  */
 197 static void ol_add_sym_to(struct ol_symlist *syml, struct ol_symhead *head,
 198                           uint64_t offset)
 199 {
 200     syml->tree.key = offset;
 201     head->tree     = rb_insert(head->tree, &syml->tree);
 202     *head->tail    = syml;
 203     head->tail     = &syml->next;
 204     head->n++;
 205 }
 206
 207 /*
 208  * Create a location structure from seg:offs
 209  */
 210 void ol_mkloc(struct ol_loc *loc, int64_t offs, int32_t seg)
 211 {
 212     nasm_zero(*loc);
 213     loc->offs = offs;
 214
 215     if (unlikely((uint32_t)seg >= SEG_ABS)) {
 216         if (likely(seg == NO_SEG)) {
 217             loc->seg.t     = OS_NOSEG;
 218         } else {
 219             loc->seg.t     = OS_ABS;
 220             loc->seg.index = seg - SEG_ABS;
 221         }
 222     } else {
 223         loc->seg.index  = seg & ~1;
 224         loc->seg.t      = OS_SECT | (seg & 1);
 225         loc->seg.s.sect = _ol_sect_by_index(loc->seg.index);
 226     }
 227 }
 228
 229 /*
 230  * Create a new symbol. If this symbol is OS_OFFS, add it to the relevant
 231  * section, too. If the symbol already exists, return NULL; this is
 232  * different from ol_get_section() as a single section may be invoked
 233  * many times. On the contrary, the front end will prevent a single symbol
 234  * from being defined more than once.
 235  *
 236  * If flags has OF_GLOBAL set, add it to the global symbol hash for
 237  * the containing section if applicable.
 238  *
 239  * If flags has OF_IMPSEC set, allocate a segment index for it via
 240  * seg_alloc() unless v->index is already set, and add it to the
 241  * section by index list.
 242  */
 243 struct ol_sym *_ol_new_sym(const char *name, const struct ol_loc *v,
 244                            uint32_t flags, size_t size)
 245 {
 246     struct hash_insert hi;
 247     struct ol_sym *sym;
 248
 249     if (hash_find(&ol_symhash, name, &hi))
 250         return NULL;            /* Symbol already exists */
 251
 252     flags     |= OF_SYMBOL;
 253
 254     sym        = nasm_zalloc(size);
 255     sym->name  = nasm_strdup(name);
 256     sym->v     = *v;
 257
 258     if (sym->v.seg.t & OS_SECT) {
 259         struct ol_sect *sect = sym->v.seg.s.sect;
 260
 261         if (!sect || (sect->flags & OF_SYMBOL))
 262             /* Must be an external or common reference */
 263             flags |= OF_IMPSEC;
 264
 265         if (flags & OF_IMPSEC) {
 266             /* Metasection */
 267             if (!sym->v.seg.s.sym) {
 268                 sym->v.seg.s.sym = sym;
 269                 sym->v.seg.index = ol_seg_alloc(sym, sym->v.seg.index);
 270             }
 271         } else if (sym->v.seg.t == OS_OFFS) {
 272             struct ol_sect * const sect = sym->v.seg.s.sect;
 273             const uint64_t offs = sym->v.offs;
 274
 275             ol_add_sym_to(&sym->syml, &sect->syml, offs);
 276             if (flags & OF_GLOBAL)
 277                 ol_add_sym_to(&sym->symg, &sect->symg, offs);
 278         }
 279     }
 280     sym->flags = flags;
 281
 282     *ol_sym_tail = sym;
 283     ol_sym_tail  = &sym->next;
 284     _ol_nsyms++;
 285
 286     hash_add(&hi, sym->name, sym);
 287     return sym;
 288 }
 289
 290 /* Find a symbol in the global namespace */
 291 struct ol_sym *_ol_sym_by_name(const char *name)
 292 {
 293     struct ol_sym **symp;
 294
 295     symp = (struct ol_sym **)hash_find(&ol_symhash, name, NULL);
 296     return symp ? *symp : NULL;
 297 }
 298
 299 /*
 300  * Find a symbol by address in a specific section. If no symbol is defined
 301  * at that exact address, return the immediately previously defined one.
 302  * If global is set, then only return global symbols.
 303  */
 304 struct ol_sym *_ol_sym_by_address(struct ol_sect *sect, int64_t addr,
 305                                   bool global)
 306 {
 307     struct ol_symhead *head;
 308     size_t t_offs;
 309     struct rbtree *t;
 310
 311     if (global) {
 312         head = &sect->symg;
 313         t_offs = offsetof(struct ol_sym, symg.tree);
 314     } else {
 315         head = &sect->syml;
 316         t_offs = offsetof(struct ol_sym, syml.tree);
 317     }
 318
 319     t = rb_search(head->tree, addr);
 320     if (!t)
 321         return NULL;
 322
 323     return (struct ol_sym *)((char *)t - t_offs);
 324 }