[RFA] record.c - save some memory in record log.

[RFA] record.c - save some memory in record log.

[Michael Snyder]

[-- Attachment #1: Type: text/plain, Size: 682 bytes --]

This change saves approximately 25 percent of memory used for
the record log in process record (my empirical measurement).

It's based on the observation that the objects that we save
(registers and small memory writes) are frequently the size of
a pointer (or smaller).  Therefore, instead of allocating both
a pointer and some malloc memory to hold them, they can simply
be saved in the space used for the pointer itself.

Saves of larger objects (bigger memory saves, or unusually
large registers) will still fall back to the old method.

This should also represent a huge saving in heap fragmentation,
since the vast majority of the mallocs would have been 4 bytes
or 8 bytes.


[-- Attachment #2: savemem.txt --]
[-- Type: text/plain, Size: 5253 bytes --]

2009-10-15  Michael Snyder  <msnyder@vmware.com>

	* record.c (struct record_reg_entry): Replace ptr with union 
	of ptr and buf.
	(struct record_mem_entry): Ditto.
	(record_reg_alloc): Don't alloc ptr if reg will fit into buf.
	(record_mem_alloc): Ditto.
	(record_reg_release): Don't free ptr if reg was stored in buf.
	(record_mem_release): Ditto.
	(record_get_loc): New function.  Return a pointer to where the
	value (mem or reg) is to be stored.
	(record_arch_list_add_reg): Call record_get_loc instead of using ptr.
	(record_arch_list_add_mem): Ditto.
	(record_wait): Ditto.

Index: record.c
===================================================================
RCS file: /cvs/src/src/gdb/record.c,v
retrieving revision 1.23
diff -u -p -r1.23 record.c
--- record.c	15 Oct 2009 17:27:54 -0000	1.23
+++ record.c	15 Oct 2009 17:48:50 -0000
@@ -43,12 +43,6 @@
    Each struct record_entry is linked to "record_list" by "prev" and
    "next" pointers.  */
 
-struct record_reg_entry
-{
-  int num;
-  gdb_byte *val;
-};
-
 struct record_mem_entry
 {
   CORE_ADDR addr;
@@ -56,7 +50,22 @@ struct record_mem_entry
   /* Set this flag if target memory for this entry
      can no longer be accessed.  */
   int mem_entry_not_accessible;
-  gdb_byte *val;
+  union
+  {
+    gdb_byte *ptr;
+    gdb_byte buf[sizeof (gdb_byte *)];
+  } u;
+};
+
+struct record_reg_entry
+{
+  unsigned short num;
+  unsigned short len;
+  union 
+  {
+    gdb_byte *ptr;
+    gdb_byte buf[2 * sizeof (gdb_byte *)];
+  } u;
 };
 
 struct record_end_entry
@@ -143,7 +152,9 @@ record_reg_alloc (struct regcache *regca
   rec = (struct record_entry *) xcalloc (1, sizeof (struct record_entry));
   rec->type = record_reg;
   rec->u.reg.num = regnum;
-  rec->u.reg.val = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
+  rec->u.reg.len = register_size (gdbarch, regnum);
+  if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
+    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
 
   return rec;
 }
@@ -154,7 +165,8 @@ static inline void
 record_reg_release (struct record_entry *rec)
 {
   gdb_assert (rec->type == record_reg);
-  xfree (rec->u.reg.val);
+  if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
+    xfree (rec->u.reg.u.ptr);
   xfree (rec);
 }
 
@@ -169,7 +181,8 @@ record_mem_alloc (CORE_ADDR addr, int le
   rec->type = record_mem;
   rec->u.mem.addr = addr;
   rec->u.mem.len = len;
-  rec->u.mem.val = (gdb_byte *) xmalloc (len);
+  if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
+    rec->u.mem.u.ptr = (gdb_byte *) xmalloc (len);
 
   return rec;
 }
@@ -180,7 +193,8 @@ static inline void
 record_mem_release (struct record_entry *rec)
 {
   gdb_assert (rec->type == record_mem);
-  xfree (rec->u.mem.val);
+  if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
+    xfree (rec->u.mem.u.ptr);
   xfree (rec);
 }
 
@@ -329,7 +343,29 @@ record_arch_list_add (struct record_entr
     }
 }
 
-/* Record the value of a register REGNUM to record_arch_list.  */
+/* Return the value storage location of a record entry.  */
+static inline gdb_byte *
+record_get_loc (struct record_entry *rec)
+{
+  switch (rec->type) {
+  case record_mem:
+    if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
+      return rec->u.mem.u.ptr;
+    else
+      return rec->u.mem.u.buf;
+  case record_reg:
+    if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
+      return rec->u.reg.u.ptr;
+    else
+      return rec->u.reg.u.buf;
+  case record_end:
+  default:
+    gdb_assert (0);
+    return NULL;
+  }
+}
+
+/* Record the value of a register NUM to record_arch_list.  */
 
 int
 record_arch_list_add_reg (struct regcache *regcache, int regnum)
@@ -344,7 +380,7 @@ record_arch_list_add_reg (struct regcach
 
   rec = record_reg_alloc (regcache, regnum);
 
-  regcache_raw_read (regcache, regnum, rec->u.reg.val);
+  regcache_raw_read (regcache, regnum, record_get_loc (rec));
 
   record_arch_list_add (rec);
 
@@ -370,7 +406,7 @@ record_arch_list_add_mem (CORE_ADDR addr
 
   rec = record_mem_alloc (addr, len);
 
-  if (target_read_memory (addr, rec->u.mem.val, len))
+  if (target_read_memory (addr, record_get_loc (rec), len))
     {
       if (record_debug)
 	fprintf_unfiltered (gdb_stdlog,
@@ -857,8 +893,9 @@ record_wait (struct target_ops *ops,
 				    record_list->u.reg.num);
 	      regcache_cooked_read (regcache, record_list->u.reg.num, reg);
 	      regcache_cooked_write (regcache, record_list->u.reg.num,
-				     record_list->u.reg.val);
-	      memcpy (record_list->u.reg.val, reg, MAX_REGISTER_SIZE);
+				     record_get_loc (record_list));
+	      memcpy (record_get_loc (record_list), reg, 
+		      record_list->u.reg.len);
 	    }
 	  else if (record_list->type == record_mem)
 	    {
@@ -892,7 +929,7 @@ record_wait (struct target_ops *ops,
 		  else
 		    {
 		      if (target_write_memory (record_list->u.mem.addr,
-					       record_list->u.mem.val,
+					       record_get_loc (record_list),
 		                               record_list->u.mem.len))
 	                {
 			  if (execution_direction != EXEC_REVERSE)
@@ -907,7 +944,7 @@ record_wait (struct target_ops *ops,
 			}
 		      else
 		        {
-			  memcpy (record_list->u.mem.val, mem,
+			  memcpy (record_get_loc (record_list), mem,
 				  record_list->u.mem.len);
 			}
 		    }

Re: [RFA] record.c - save some memory in record log.

[Joel Brobecker]

> It's based on the observation that the objects that we save
> (registers and small memory writes) are frequently the size of
> a pointer (or smaller).  Therefore, instead of allocating both
> a pointer and some malloc memory to hold them, they can simply
> be saved in the space used for the pointer itself.

One way that we have used in the past that might be helpful here
is to define the buffer at the end of the structure and without
the pointer indirection:

   struct blah
   {
     ...

     int buffer_len;
     gdb_byte buf[0];
   };

The allocation of the structure become a little trickier. And access
to the buffer is a little more dangerous, which is why I don't like
this approach much.  But it does save memory, and you can prevent
buffer overrun by forcing access to this data through accessor
routines...

-- 
Joel

Re: [RFA] record.c - save some memory in record log.

[Hui Zhu]

Thanks Michael, This patch is very cool.

+struct record_reg_entry
+{
+  unsigned short num;
+  unsigned short len;
+  union
+  {
+    gdb_byte *ptr;
+    gdb_byte buf[2 * sizeof (gdb_byte *)];

Why this part use "2 * sizeof (gdb_byte *)"?

+    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
I suggest change MAX_REGISTER_SIZE to rec->u.reg.len.


Thanks,
Hui

On Fri, Oct 16, 2009 at 01:53, Michael Snyder <msnyder@vmware.com> wrote:
> This change saves approximately 25 percent of memory used for
> the record log in process record (my empirical measurement).
>
> It's based on the observation that the objects that we save
> (registers and small memory writes) are frequently the size of
> a pointer (or smaller).  Therefore, instead of allocating both
> a pointer and some malloc memory to hold them, they can simply
> be saved in the space used for the pointer itself.
>
> Saves of larger objects (bigger memory saves, or unusually
> large registers) will still fall back to the old method.
>
> This should also represent a huge saving in heap fragmentation,
> since the vast majority of the mallocs would have been 4 bytes
> or 8 bytes.
>
>
> 2009-10-15  Michael Snyder  <msnyder@vmware.com>
>
>        * record.c (struct record_reg_entry): Replace ptr with union
>        of ptr and buf.
>        (struct record_mem_entry): Ditto.
>        (record_reg_alloc): Don't alloc ptr if reg will fit into buf.
>        (record_mem_alloc): Ditto.
>        (record_reg_release): Don't free ptr if reg was stored in buf.
>        (record_mem_release): Ditto.
>        (record_get_loc): New function.  Return a pointer to where the
>        value (mem or reg) is to be stored.
>        (record_arch_list_add_reg): Call record_get_loc instead of using ptr.
>        (record_arch_list_add_mem): Ditto.
>        (record_wait): Ditto.
>
> Index: record.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/record.c,v
> retrieving revision 1.23
> diff -u -p -r1.23 record.c
> --- record.c    15 Oct 2009 17:27:54 -0000      1.23
> +++ record.c    15 Oct 2009 17:48:50 -0000
> @@ -43,12 +43,6 @@
>    Each struct record_entry is linked to "record_list" by "prev" and
>    "next" pointers.  */
>
> -struct record_reg_entry
> -{
> -  int num;
> -  gdb_byte *val;
> -};
> -
>  struct record_mem_entry
>  {
>   CORE_ADDR addr;
> @@ -56,7 +50,22 @@ struct record_mem_entry
>   /* Set this flag if target memory for this entry
>      can no longer be accessed.  */
>   int mem_entry_not_accessible;
> -  gdb_byte *val;
> +  union
> +  {
> +    gdb_byte *ptr;
> +    gdb_byte buf[sizeof (gdb_byte *)];
> +  } u;
> +};
> +
> +struct record_reg_entry
> +{
> +  unsigned short num;
> +  unsigned short len;
> +  union
> +  {
> +    gdb_byte *ptr;
> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
> +  } u;
>  };
>
>  struct record_end_entry
> @@ -143,7 +152,9 @@ record_reg_alloc (struct regcache *regca
>   rec = (struct record_entry *) xcalloc (1, sizeof (struct record_entry));
>   rec->type = record_reg;
>   rec->u.reg.num = regnum;
> -  rec->u.reg.val = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
> +  rec->u.reg.len = register_size (gdbarch, regnum);
> +  if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
> +    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
>
>   return rec;
>  }
> @@ -154,7 +165,8 @@ static inline void
>  record_reg_release (struct record_entry *rec)
>  {
>   gdb_assert (rec->type == record_reg);
> -  xfree (rec->u.reg.val);
> +  if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
> +    xfree (rec->u.reg.u.ptr);
>   xfree (rec);
>  }
>
> @@ -169,7 +181,8 @@ record_mem_alloc (CORE_ADDR addr, int le
>   rec->type = record_mem;
>   rec->u.mem.addr = addr;
>   rec->u.mem.len = len;
> -  rec->u.mem.val = (gdb_byte *) xmalloc (len);
> +  if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
> +    rec->u.mem.u.ptr = (gdb_byte *) xmalloc (len);
>
>   return rec;
>  }
> @@ -180,7 +193,8 @@ static inline void
>  record_mem_release (struct record_entry *rec)
>  {
>   gdb_assert (rec->type == record_mem);
> -  xfree (rec->u.mem.val);
> +  if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
> +    xfree (rec->u.mem.u.ptr);
>   xfree (rec);
>  }
>
> @@ -329,7 +343,29 @@ record_arch_list_add (struct record_entr
>     }
>  }
>
> -/* Record the value of a register REGNUM to record_arch_list.  */
> +/* Return the value storage location of a record entry.  */
> +static inline gdb_byte *
> +record_get_loc (struct record_entry *rec)
> +{
> +  switch (rec->type) {
> +  case record_mem:
> +    if (rec->u.mem.len > sizeof (rec->u.mem.u.buf))
> +      return rec->u.mem.u.ptr;
> +    else
> +      return rec->u.mem.u.buf;
> +  case record_reg:
> +    if (rec->u.reg.len > sizeof (rec->u.reg.u.buf))
> +      return rec->u.reg.u.ptr;
> +    else
> +      return rec->u.reg.u.buf;
> +  case record_end:
> +  default:
> +    gdb_assert (0);
> +    return NULL;
> +  }
> +}
> +
> +/* Record the value of a register NUM to record_arch_list.  */
>
>  int
>  record_arch_list_add_reg (struct regcache *regcache, int regnum)
> @@ -344,7 +380,7 @@ record_arch_list_add_reg (struct regcach
>
>   rec = record_reg_alloc (regcache, regnum);
>
> -  regcache_raw_read (regcache, regnum, rec->u.reg.val);
> +  regcache_raw_read (regcache, regnum, record_get_loc (rec));
>
>   record_arch_list_add (rec);
>
> @@ -370,7 +406,7 @@ record_arch_list_add_mem (CORE_ADDR addr
>
>   rec = record_mem_alloc (addr, len);
>
> -  if (target_read_memory (addr, rec->u.mem.val, len))
> +  if (target_read_memory (addr, record_get_loc (rec), len))
>     {
>       if (record_debug)
>        fprintf_unfiltered (gdb_stdlog,
> @@ -857,8 +893,9 @@ record_wait (struct target_ops *ops,
>                                    record_list->u.reg.num);
>              regcache_cooked_read (regcache, record_list->u.reg.num, reg);
>              regcache_cooked_write (regcache, record_list->u.reg.num,
> -                                    record_list->u.reg.val);
> -             memcpy (record_list->u.reg.val, reg, MAX_REGISTER_SIZE);
> +                                    record_get_loc (record_list));
> +             memcpy (record_get_loc (record_list), reg,
> +                     record_list->u.reg.len);
>            }
>          else if (record_list->type == record_mem)
>            {
> @@ -892,7 +929,7 @@ record_wait (struct target_ops *ops,
>                  else
>                    {
>                      if (target_write_memory (record_list->u.mem.addr,
> -                                              record_list->u.mem.val,
> +                                              record_get_loc (record_list),
>                                               record_list->u.mem.len))
>                        {
>                          if (execution_direction != EXEC_REVERSE)
> @@ -907,7 +944,7 @@ record_wait (struct target_ops *ops,
>                        }
>                      else
>                        {
> -                         memcpy (record_list->u.mem.val, mem,
> +                         memcpy (record_get_loc (record_list), mem,
>                                  record_list->u.mem.len);
>                        }
>                    }
>
>

Re: [RFA] record.c - save some memory in record log.

[Hui Zhu]

>
> One way that we have used in the past that might be helpful here
> is to define the buffer at the end of the structure and without
> the pointer indirection:
>
>   struct blah
>   {
>     ...
>
>     int buffer_len;
>     gdb_byte buf[0];
>   };
>
> The allocation of the structure become a little trickier. And access
> to the buffer is a little more dangerous, which is why I don't like
> this approach much.  But it does save memory, and you can prevent
> buffer overrun by forcing access to this data through accessor
> routines...
>

Hi Joel,

But I think:
+  union
+  {
+    gdb_byte *ptr;
+    gdb_byte buf[2 * sizeof (gdb_byte *)];

Make the size of buf more clear.

Thanks,
Hui

Re: [RFA] record.c - save some memory in record log.

[Michael Snyder]

Hui Zhu wrote:
> Thanks Michael, This patch is very cool.
> 
> +struct record_reg_entry
> +{
> +  unsigned short num;
> +  unsigned short len;
> +  union
> +  {
> +    gdb_byte *ptr;
> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
> 
> Why this part use "2 * sizeof (gdb_byte *)"?

Oh, no strong reason.  I just noticed that mem_entry is larger
than reg_entry, and since it is used in a union, that space is
otherwise going to waste.

I do not assume that a target general register is the same size
as a host pointer -- only that the larger we make this buf, the
less likely that we have to use malloc.

> 
> +    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
> I suggest change MAX_REGISTER_SIZE to rec->u.reg.len.

Ah, good idea, thanks.  I'll make that change.

Any other comments?

Re: [RFA] record.c - save some memory in record log.

[Hui Zhu]

Thanks Michael, I am OK with it.

Hui

On Sun, Oct 18, 2009 at 11:50, Michael Snyder <msnyder@vmware.com> wrote:
> Hui Zhu wrote:
>>
>> Thanks Michael, This patch is very cool.
>>
>> +struct record_reg_entry
>> +{
>> +  unsigned short num;
>> +  unsigned short len;
>> +  union
>> +  {
>> +    gdb_byte *ptr;
>> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
>>
>> Why this part use "2 * sizeof (gdb_byte *)"?
>
> Oh, no strong reason.  I just noticed that mem_entry is larger
> than reg_entry, and since it is used in a union, that space is
> otherwise going to waste.
>
> I do not assume that a target general register is the same size
> as a host pointer -- only that the larger we make this buf, the
> less likely that we have to use malloc.
>
>>
>> +    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
>> I suggest change MAX_REGISTER_SIZE to rec->u.reg.len.
>
> Ah, good idea, thanks.  I'll make that change.
>
> Any other comments?
>
>

Re: [RFA] record.c - save some memory in record log.

[Joel Brobecker]

> But I think:

Note that I was just idly mentioning a trick I saw us use in the past,
but it's definitely ok if you guys think it's a bad idea.

> +  union
> +  {
> +    gdb_byte *ptr;
> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
> 
> Make the size of buf more clear.

The problem with this approach is that the size of the union is the
maximum of all its components.  So the size of your union is always
going to be 8/16 bytes, depending on whether addresses are 4 or 8 bytes.
Unless buf was meant to be a 2-bytes buffer, then the size is always
going to be 4 bytes.

With the trick I provided, the size is always going to be exactly as
much as you need.  But, like I said, it's not exactly super clean...

-- 
Joel

Re: [RFA] record.c - save some memory in record log.

[Michael Snyder]

Hui Zhu wrote:
> Thanks Michael, I am OK with it.

Great!  Committed, thanks!

> On Sun, Oct 18, 2009 at 11:50, Michael Snyder <msnyder@vmware.com> wrote:
>> Hui Zhu wrote:
>>> Thanks Michael, This patch is very cool.
>>>
>>> +struct record_reg_entry
>>> +{
>>> +  unsigned short num;
>>> +  unsigned short len;
>>> +  union
>>> +  {
>>> +    gdb_byte *ptr;
>>> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
>>>
>>> Why this part use "2 * sizeof (gdb_byte *)"?
>> Oh, no strong reason.  I just noticed that mem_entry is larger
>> than reg_entry, and since it is used in a union, that space is
>> otherwise going to waste.
>>
>> I do not assume that a target general register is the same size
>> as a host pointer -- only that the larger we make this buf, the
>> less likely that we have to use malloc.
>>
>>> +    rec->u.reg.u.ptr = (gdb_byte *) xmalloc (MAX_REGISTER_SIZE);
>>> I suggest change MAX_REGISTER_SIZE to rec->u.reg.len.
>> Ah, good idea, thanks.  I'll make that change.
>>
>> Any other comments?
>>
>>
> 

Re: [RFA] record.c - save some memory in record log.

[Michael Snyder]

Joel Brobecker wrote:
>> But I think:
> 
> Note that I was just idly mentioning a trick I saw us use in the past,
> but it's definitely ok if you guys think it's a bad idea.
> 
>> +  union
>> +  {
>> +    gdb_byte *ptr;
>> +    gdb_byte buf[2 * sizeof (gdb_byte *)];
>>
>> Make the size of buf more clear.
> 
> The problem with this approach is that the size of the union is the
> maximum of all its components.  So the size of your union is always
> going to be 8/16 bytes, depending on whether addresses are 4 or 8 bytes.
> Unless buf was meant to be a 2-bytes buffer, then the size is always
> going to be 4 bytes.
> 
> With the trick I provided, the size is always going to be exactly as
> much as you need.  But, like I said, it's not exactly super clean...
> 

Joel, it's a work in progress.  ;-)

I see the change I made as having made the data structure
incrementally better.  There's always room for a further change
that makes it better still.