[rfc] Use vec.h to revise memattr.[ch]
Daniel Jacobowitz
drow@false.org
Tue Aug 15 19:58:00 GMT 2006
This patch handles a FIXME from memattr.h:
- /* FIXME: memory regions are stored in an unsorted singly-linked
- list. This probably won't scale to handle hundreds of memory
- regions --- that many could be needed to describe the allowed
- access modes for memory mapped i/o device registers. */
- struct mem_region *next;
Using a linked list to handle dynamic arrays is very simple in C, which
is why GDB has so many of them. One of the big advantages of vec.h is
that it makes having typesafe resizable arrays much simpler, and works
efficiently with them. This patch converts memattr.h to the new
interface. It removes one linear search which can now be done as a
binary search:
+ new.lo = lo;
+ new.hi = hi;
+
+ ix = VEC_lower_bound (mem_region_s, mem_region_list, &new,
+ mem_region_lessthan);
+
+ /* Check for an overlapping memory region. We only need to check
+ in the vicinity - at most one before and one after the
+ insertion point. */
+ for (i = ix - 1; i < ix + 1; i++)
It also simplifies removing an item:
+ VEC_ordered_remove (mem_region_s, mem_region_list, ix);
Of course, there are tradeoffs. I chose to store the list sorted.
That means that the ordered remove has to shuffle a bunch of following
items downwards, and the insertion has to shuffle them upwards. But
these are for user-typed "mem" and "delete mem" commands, which are
relatively infrequent; I think this is an appropriate data structure.
More important will be using a binary search in lookup_mem_region,
which I didn't implement, but which would be quite easy now.
An interesting note is that this is a vector of structs, rather than
pointers to structs. The VEC interface is happy creating either;
one advantage of pointers to objects is that you don't need to handle
as frequent memory allocation.
This isn't an important patch on its own merits. It's useful for the
upcoming flash patches, which I've revised to integrate with "info
mem" - they build memory maps from XML and they happened to already
be using vectors - and as an example of how to use vec.h.
Any comments? I think it's a net improvement in clarity.
--
Daniel Jacobowitz
CodeSourcery
2006-08-15 Daniel Jacobowitz <dan@codesourcery.com>
* Makefile.in (memattr_h, memattr.o): Update.
* memattr.h: Include "vec.h".
(struct mem_region): Remove linked list pointer.
(mem_region_s): New typedef and corresponding vector.
* memattr.c: Include "vec.h".
(mem_region_chain): Delete.
(mem_region_list): New vector pointer.
(mem_region_lessthan): New function.
(create_mem_region): Remove unused return value. Use vector
operations. Remove linear search.
(delete_mem_region): Delete.
(lookup_mem_region): Use vector operations. Add a FIXME.
(mem_info_command): Update to work with vectors.
(mem_enable, mem_enable_command, mem_disable, mem_disable_command)
(mem_free, mem_delete): Likewise.
---
gdb/Makefile.in | 4 -
gdb/memattr.c | 128 ++++++++++++++++++++++++++++++--------------------------
gdb/memattr.h | 17 ++++---
3 files changed, 82 insertions(+), 67 deletions(-)
Index: src/gdb/memattr.c
===================================================================
--- src.orig/gdb/memattr.c 2006-08-10 23:21:32.000000000 -0400
+++ src/gdb/memattr.c 2006-08-11 10:31:56.000000000 -0400
@@ -1,6 +1,7 @@
/* Memory attributes support, for GDB.
- Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+ Free Software Foundation, Inc.
This file is part of GDB.
@@ -26,6 +27,7 @@
#include "target.h"
#include "value.h"
#include "language.h"
+#include "vec.h"
#include "gdb_string.h"
const struct mem_attrib default_mem_attrib =
@@ -37,54 +39,66 @@ const struct mem_attrib default_mem_attr
0 /* verify */
};
-static struct mem_region *mem_region_chain = NULL;
+VEC(mem_region_s) *mem_region_list;
static int mem_number = 0;
-static struct mem_region *
+/* Predicate function which returns true if LHS should sort before RHS
+ in a list of memory regions, useful for VEC_lower_bound. */
+
+static int
+mem_region_lessthan (const struct mem_region *lhs,
+ const struct mem_region *rhs)
+{
+ return lhs->lo < rhs->lo;
+}
+
+static void
create_mem_region (CORE_ADDR lo, CORE_ADDR hi,
const struct mem_attrib *attrib)
{
- struct mem_region *n, *new;
+ struct mem_region new;
+ int i, ix;
/* lo == hi is a useless empty region */
if (lo >= hi && hi != 0)
{
printf_unfiltered (_("invalid memory region: low >= high\n"));
- return NULL;
+ return;
}
- n = mem_region_chain;
- while (n)
+ new.lo = lo;
+ new.hi = hi;
+
+ ix = VEC_lower_bound (mem_region_s, mem_region_list, &new,
+ mem_region_lessthan);
+
+ /* Check for an overlapping memory region. We only need to check
+ in the vicinity - at most one before and one after the
+ insertion point. */
+ for (i = ix - 1; i < ix + 1; i++)
{
- /* overlapping node */
+ struct mem_region *n;
+
+ if (i < 0)
+ continue;
+ if (i >= VEC_length (mem_region_s, mem_region_list))
+ continue;
+
+ n = VEC_index (mem_region_s, mem_region_list, i);
+
if ((lo >= n->lo && (lo < n->hi || n->hi == 0))
|| (hi > n->lo && (hi <= n->hi || n->hi == 0))
|| (lo <= n->lo && (hi >= n->hi || hi == 0)))
{
printf_unfiltered (_("overlapping memory region\n"));
- return NULL;
+ return;
}
- n = n->next;
}
- new = xmalloc (sizeof (struct mem_region));
- new->lo = lo;
- new->hi = hi;
- new->number = ++mem_number;
- new->enabled_p = 1;
- new->attrib = *attrib;
-
- /* link in new node */
- new->next = mem_region_chain;
- mem_region_chain = new;
-
- return new;
-}
-
-static void
-delete_mem_region (struct mem_region *m)
-{
- xfree (m);
+ new.number = ++mem_number;
+ new.enabled_p = 1;
+ new.attrib = *attrib;
+ VEC_safe_insert (mem_region_s, mem_region_list, ix, &new);
}
/*
@@ -97,6 +111,7 @@ lookup_mem_region (CORE_ADDR addr)
struct mem_region *m;
CORE_ADDR lo;
CORE_ADDR hi;
+ int ix;
/* First we initialize LO and HI so that they describe the entire
memory space. As we process the memory region chain, they are
@@ -108,7 +123,10 @@ lookup_mem_region (CORE_ADDR addr)
lo = (CORE_ADDR) 0;
hi = (CORE_ADDR) ~ 0;
- for (m = mem_region_chain; m; m = m->next)
+ /* If we ever want to support a huge list of memory regions, this
+ check should be replaced with a binary search (probably using
+ VEC_lower_bound). */
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
{
if (m->enabled_p == 1)
{
@@ -215,8 +233,9 @@ mem_info_command (char *args, int from_t
{
struct mem_region *m;
struct mem_attrib *attrib;
+ int ix;
- if (!mem_region_chain)
+ if (!mem_region_list)
{
printf_unfiltered (_("There are no memory regions defined.\n"));
return;
@@ -233,7 +252,7 @@ mem_info_command (char *args, int from_t
printf_filtered ("Attrs ");
printf_filtered ("\n");
- for (m = mem_region_chain; m; m = m->next)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
{
char *tmp;
printf_filtered ("%-3d %-3c\t",
@@ -339,8 +358,9 @@ static void
mem_enable (int num)
{
struct mem_region *m;
+ int ix;
- for (m = mem_region_chain; m; m = m->next)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
if (m->number == num)
{
m->enabled_p = 1;
@@ -356,12 +376,13 @@ mem_enable_command (char *args, int from
char *p1;
int num;
struct mem_region *m;
+ int ix;
dcache_invalidate (target_dcache);
if (p == 0)
{
- for (m = mem_region_chain; m; m = m->next)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
m->enabled_p = 1;
}
else
@@ -389,8 +410,9 @@ static void
mem_disable (int num)
{
struct mem_region *m;
+ int ix;
- for (m = mem_region_chain; m; m = m->next)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
if (m->number == num)
{
m->enabled_p = 0;
@@ -406,12 +428,13 @@ mem_disable_command (char *args, int fro
char *p1;
int num;
struct mem_region *m;
+ int ix;
dcache_invalidate (target_dcache);
if (p == 0)
{
- for (m = mem_region_chain; m; m = m->next)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
m->enabled_p = 0;
}
else
@@ -437,13 +460,7 @@ mem_disable_command (char *args, int fro
static void
mem_clear (void)
{
- struct mem_region *m;
-
- while ((m = mem_region_chain) != 0)
- {
- mem_region_chain = m->next;
- delete_mem_region (m);
- }
+ VEC_free (mem_region_s, mem_region_list);
}
/* Delete the memory region number NUM. */
@@ -452,30 +469,25 @@ static void
mem_delete (int num)
{
struct mem_region *m1, *m;
+ int ix;
- if (!mem_region_chain)
+ if (!mem_region_list)
{
printf_unfiltered (_("No memory region number %d.\n"), num);
return;
}
- if (mem_region_chain->number == num)
+ for (ix = 0; VEC_iterate (mem_region_s, mem_region_list, ix, m); ix++)
+ if (m->number == num)
+ break;
+
+ if (m == NULL)
{
- m1 = mem_region_chain;
- mem_region_chain = m1->next;
- delete_mem_region (m1);
+ printf_unfiltered (_("No memory region number %d.\n"), num);
+ return;
}
- else
- for (m = mem_region_chain; m->next; m = m->next)
- {
- if (m->next->number == num)
- {
- m1 = m->next;
- m->next = m1->next;
- delete_mem_region (m1);
- break;
- }
- }
+
+ VEC_ordered_remove (mem_region_s, mem_region_list, ix);
}
static void
Index: src/gdb/memattr.h
===================================================================
--- src.orig/gdb/memattr.h 2006-08-10 23:21:32.000000000 -0400
+++ src/gdb/memattr.h 2006-08-11 10:31:56.000000000 -0400
@@ -1,5 +1,6 @@
/* Memory attributes support, for GDB.
- Copyright (C) 2001 Free Software Foundation, Inc.
+
+ Copyright (C) 2001, 2006 Free Software Foundation, Inc.
This file is part of GDB.
@@ -21,6 +22,8 @@
#ifndef MEMATTR_H
#define MEMATTR_H
+#include "vec.h"
+
enum mem_access_mode
{
MEM_RW, /* read/write */
@@ -67,12 +70,6 @@ struct mem_attrib
struct mem_region
{
- /* FIXME: memory regions are stored in an unsorted singly-linked
- list. This probably won't scale to handle hundreds of memory
- regions --- that many could be needed to describe the allowed
- access modes for memory mapped i/o device registers. */
- struct mem_region *next;
-
CORE_ADDR lo;
CORE_ADDR hi;
@@ -86,6 +83,12 @@ struct mem_region
struct mem_attrib attrib;
};
+/* Declare a vector type for a group of mem_region structures. The
+ typedef is necessary because vec.h can not handle a struct tag.
+ Except during construction, these vectors are kept sorted. */
+typedef struct mem_region mem_region_s;
+DEF_VEC_O(mem_region_s);
+
extern struct mem_region *lookup_mem_region(CORE_ADDR);
#endif /* MEMATTR_H */
Index: src/gdb/Makefile.in
===================================================================
--- src.orig/gdb/Makefile.in 2006-08-10 23:31:20.000000000 -0400
+++ src/gdb/Makefile.in 2006-08-11 10:31:56.000000000 -0400
@@ -743,7 +743,7 @@ macroscope_h = macroscope.h $(macrotab_h
macrotab_h = macrotab.h
main_h = main.h
mdebugread_h = mdebugread.h $(coff_sym_h) $(coff_symconst_h)
-memattr_h = memattr.h
+memattr_h = memattr.h $(vec_h)
mips_linux_tdep_h = mips-linux-tdep.h
mips_mdebug_tdep_h = mips-mdebug-tdep.h
mipsnbsd_tdep_h = mipsnbsd-tdep.h
@@ -2323,7 +2323,7 @@ mdebugread.o: mdebugread.c $(defs_h) $(s
$(bfd_h) $(coff_ecoff_h) $(libaout_h) $(aout_aout64_h) \
$(aout_stab_gnu_h) $(expression_h)
memattr.o: memattr.c $(defs_h) $(command_h) $(gdbcmd_h) $(memattr_h) \
- $(target_h) $(value_h) $(language_h) $(gdb_string_h)
+ $(target_h) $(value_h) $(language_h) $(vec_h) $(gdb_string_h)
mem-break.o: mem-break.c $(defs_h) $(symtab_h) $(breakpoint_h) $(inferior_h) \
$(target_h)
mingw-hdep.o: mingw-hdep.c $(defs_h) $(serial_h) $(gdb_assert_h) \
More information about the Gdb-patches
mailing list