--- a/src/dwarf2-abbrev.c Sun Aug 01 23:54:08 2010 +0200
+++ b/src/dwarf2-abbrev.c Sun Aug 01 23:54:31 2010 +0200
@@ -23,7 +23,7 @@
#include <assert.h>
-#define nopeABBREV_DEBUG 1
+#define noABBREV_DEBUG 1
#ifdef ABBREV_DEBUG
#include <stdio.h>
#define ABBREV_DEBUG_PRINTF(str, ...) \
@@ -32,7 +32,7 @@
#define ABBREV_DEBUG_PRINTF(str, ...)
#endif
-#define nopeCACHE_DEBUG 1
+#define noCACHE_DEBUG 1
#ifdef CACHE_DEBUG
#include <stdio.h>
#define CACHE_DEBUG_PRINTF(str, ...) \
@@ -41,99 +41,114 @@
#define CACHE_DEBUG_PRINTF(str, ...)
#endif
-
-
-#define get_occupied(x) (x&0x80)
-#define get_value(x) ((uint8_t)x&0x7f)
-
-static int
+static inline int
cache_try_lookup (uint64_t key, uint32_t *value, struct cache *cache)
{
- uint8_t start_slot, i, backup_slot, backup_key;
+ uint8_t start_slot = (uint8_t) key % CACHE_SIZE;
+ struct cache_entry *begin = &cache->entries[start_slot];
+ struct cache_entry *end = &cache->entries[CACHE_SIZE];
+ struct cache_entry *backup_entry = 0;
+ struct cache_entry *entry;
+
cache->time++;
- start_slot = (uint8_t) (key - 1) % CACHE_SIZE;
- i = start_slot;
- backup_key = 0;
- backup_slot = 0;
- do {
- if (get_occupied (cache->keys[i])) {
- if (get_value (cache->keys[i]) == get_value (key)) {
+ restart:
+ for (entry = begin; entry != end; entry++) {
+ if (entry->occupied) {
+ if (entry->key == key) {
/* found slot */
- CACHE_DEBUG_PRINTF ("found %d at %d\n", get_value (key), i);
- cache->last_used[i] = cache->time;
- *value = cache->values[i];
- return 0;
- } else if (get_value (cache->keys[i]) < get_value (key) &&
- get_value (cache->keys[i]) > backup_key) {
- backup_key = get_value (cache->keys[i]);
- backup_slot = i;
+ CACHE_DEBUG_PRINTF ("found %d at %d\n", (int)key, i);
+ entry->last_used = cache->time;
+ *value = entry->value;
+ return 1;
+ } else if (entry->key < key
+ && (backup_entry == 0
+ || entry->key > backup_entry->key)) {
+ backup_entry = entry;
}
}
- i++;
- i %= CACHE_SIZE;
- } while (i != start_slot);
+ }
+ if (entry == &cache->entries[CACHE_SIZE]) {
+ end = begin;
+ begin = &cache->entries[0];
+ goto restart;
+ }
/* did not find the key in the cache after looking
- * in every entry. Try to return the highest
+ * at every entry. Try to return the highest
* key which is smaller than the requested key.
* It is stored in backup_slot.
*/
- if (backup_key > 0) {
- cache->last_used[backup_slot] = cache->time;
- *value = cache->values[backup_slot];
- CACHE_DEBUG_PRINTF ("found backup %d at %d for %llu\n", backup_key, backup_slot, key);
- return 0;
+ if (backup_entry != 0) {
+ backup_entry->last_used = cache->time;
+ *value = backup_entry->value;
+ CACHE_DEBUG_PRINTF ("found backup %d for %llu\n",
+ backup_entry->key, key);
+ return 1;
} else {
CACHE_DEBUG_PRINTF ("did not find %llu\n", key);
- return -1;
+ return 0;
}
}
-static uint8_t
+static inline struct cache_entry *
cache_search_lru_location (struct cache *cache)
{
- uint8_t lru, location, i;
- location = 0;
- lru = cache->time;
- for (i = 0; i < CACHE_SIZE; i++) {
- if (cache->last_used[i] < lru) {
- lru = cache->last_used[i];
- location = i;
+ struct cache_entry *begin = &cache->entries[0];
+ struct cache_entry *end = &cache->entries[CACHE_SIZE];
+ struct cache_entry *entry;
+ struct cache_entry *lru = begin;
+ uint8_t lru_time = cache->time;
+ for (entry = begin; entry != end; entry++) {
+ if (entry->last_used < lru_time) {
+ lru_time = entry->last_used;
+ lru = entry;
}
}
- return location;
+ return lru;
}
-static void
+static inline void
cache_try_add (uint64_t key, uint32_t value, struct cache *cache)
{
- uint8_t start_slot, i, lru;
+ uint8_t start_slot = (uint8_t) key % CACHE_SIZE;
+ struct cache_entry *begin = &cache->entries[start_slot];
+ struct cache_entry *end = &cache->entries[CACHE_SIZE];
+ struct cache_entry *entry;
+ struct cache_entry *lru;
+
+ if (begin->value == value) {
+ goto ok;
+ }
cache->time++;
- start_slot = (uint8_t) (key - 1) % CACHE_SIZE;
- i = start_slot;
- do {
- if (!get_occupied (cache->keys[i])) {
+ restart:
+ for (entry = begin; entry != end; entry++) {
+ if (!entry->occupied) {
/* reached empty slot
* add item.
*/
- CACHE_DEBUG_PRINTF ("add %d at %d, start: %d\n", get_value (key), i, start_slot);
- cache->keys[i] = 0x80 | get_value (key);
- cache->values[i] = value;
- cache->last_used[i] = cache->time;
+ CACHE_DEBUG_PRINTF ("add %d start: %d\n",
+ key, start_slot);
+ entry->key = key;
+ entry->value = value;
+ entry->last_used = cache->time;
+ entry->occupied = 1;
goto ok;
}
- i++;
- i %= CACHE_SIZE;
- } while (i != start_slot);
+ }
+ if (entry == &cache->entries[CACHE_SIZE]) {
+ end = begin;
+ begin = &cache->entries[0];
+ goto restart;
+ }
/* no empty slot. replace the Least Recently Used
* with this entry.
*/
lru = cache_search_lru_location (cache);
- cache->keys[lru] = 0x80 | get_value (key);
- cache->values[lru] = value;
- cache->last_used[lru] = cache->time;
- CACHE_DEBUG_PRINTF ("add full %d at %d\n", get_value (key), i);
+ lru->key = key;
+ lru->value = value;
+ lru->last_used = cache->time;
+ CACHE_DEBUG_PRINTF ("add full %d\n", key);
ok:
return;
}
@@ -145,25 +160,18 @@
}
-
-enum search_abbrev_e {
- SEARCH_BY_TAG,
- SEARCH_BY_CODE
-};
-
/* see section 7.5.3 dwarf2 p67 */
static bool
-search_abbrev_start_to_end (uint64_t searched_id, enum search_abbrev_e search_type,
+search_abbrev_start_to_end (uint64_t searched_id,
uint32_t start, uint32_t end, uint32_t*retval,
struct reader *reader)
{
+ uint64_t abbr_code, name, form;
+ uint8_t children;
+ uint32_t offset;
+ int n = 0;
reader_seek (reader, start);
-
- while (reader_get_offset (reader) < end) {
- uint64_t abbr_code, tag, name, form;
- uint8_t children;
- uint32_t offset;
- offset = reader_get_offset (reader);
+ while ((offset = reader_get_offset (reader)) < end) {
abbr_code = reader_read_uleb128 (reader);
ABBREV_DEBUG_PRINTF ("%llu ", abbr_code);
if (abbr_code == 0) {
@@ -173,16 +181,16 @@
*/
break;
}
- tag = reader_read_uleb128 (reader);
- children = reader_read_u8 (reader);
-
- if ((search_type == SEARCH_BY_TAG && searched_id == tag) ||
- (search_type == SEARCH_BY_CODE && searched_id == abbr_code)) {
+ if (searched_id == abbr_code) {
*retval = offset;
ABBREV_DEBUG_PRINTF ("\n");
- ABBREV_DEBUG_PRINTF ("input: %llu, output: %u\n", searched_id, *retval);
+ ABBREV_DEBUG_PRINTF ("input: %llu, output: %u n: %d\n",
+ searched_id, *retval, n);
return true;
}
+ n++;
+ reader_skip_uleb128 (reader);
+ children = reader_read_u8 (reader);
/* skip the attribute specification */
do {
@@ -221,41 +229,34 @@
uint64_t abbr_code,
struct reader *reader)
{
- uint32_t abbrev_start;
- uint32_t abbrev_end;
- uint32_t abbrev_offset;
+ uint32_t abbrev_start = abbrev_cu->start;
+ uint32_t abbrev_end = abbrev_cu->end;
+ uint32_t abbrev_offset = abbrev_cu->start;
- abbrev_start = abbrev_cu->start;
- abbrev_end = abbrev_cu->end;
+ cache_try_lookup (abbr_code, &abbrev_offset, &abbrev_cu->cache);
- if (cache_try_lookup (abbr_code, &abbrev_offset, &abbrev_cu->cache) == -1) {
- abbrev_offset = abbrev_start;
- }
- reader_seek (reader, abbrev_offset);
- if (reader_read_uleb128 (reader) != abbr_code) {
- if (search_abbrev_start_to_end (abbr_code, SEARCH_BY_CODE,
- abbrev_offset, abbrev_end,
- &abbrev_offset,
- reader)) {
- /* found abbr_code from abbrev_offset to abbrev_end */
- cache_try_add (abbr_code, abbrev_offset, &abbrev_cu->cache);
- } else if (abbrev_offset == abbrev_start) {
- /* did not find abbr_code from abbrev_start to abbrev_end */
- goto error;
- } else if (search_abbrev_start_to_end (abbr_code, SEARCH_BY_CODE,
- abbrev_start, abbrev_offset,
- &abbrev_offset,
- reader)) {
- /* found abbr_code from abbrev_start to abbrev_offset */
- cache_try_add (abbr_code, abbrev_offset, &abbrev_cu->cache);
- } else {
- /* Did not find abbr_code from
- * - abbrev_offset to abbrev_end
- * - abbrev_start to abbrev_offset
- * where abbrev_start <= abbrev_offset <= abbrev_end
- */
- goto error;
- }
+ if (search_abbrev_start_to_end (abbr_code,
+ abbrev_offset, abbrev_end,
+ &abbrev_offset,
+ reader)) {
+ /* found abbr_code from abbrev_offset to abbrev_end */
+ cache_try_add (abbr_code, abbrev_offset, &abbrev_cu->cache);
+ } else if (abbrev_offset == abbrev_start) {
+ /* did not find abbr_code from abbrev_start to abbrev_end */
+ goto error;
+ } else if (search_abbrev_start_to_end (abbr_code,
+ abbrev_start, abbrev_offset,
+ &abbrev_offset,
+ reader)) {
+ /* found abbr_code from abbrev_start to abbrev_offset */
+ cache_try_add (abbr_code, abbrev_offset, &abbrev_cu->cache);
+ } else {
+ /* Did not find abbr_code from
+ * - abbrev_offset to abbrev_end
+ * - abbrev_start to abbrev_offset
+ * where abbrev_start <= abbrev_offset <= abbrev_end
+ */
+ goto error;
}
decl->offset = abbrev_offset;
reader_seek (reader, abbrev_offset);