gettext.c patch: reuse memory

gettext.c patch: reuse memory

[Carles Pina i Estany]

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


Hello,

This week I realised of a quite big mistake in the gettext module. Every
time that the user of this module was asking for string translation,
gettext module was allocating new memory and returning it. So if the
user was asking 10 times for the same string, gettext was creating 10
new strings and leaking memory.

With the attached patch, gettext module saves in a list the
translations.  So if a user asks again for the same translation it
returns the same pointer to the already allocated string instead of a
new one.

If someone wants to discuss things maybe in the IRC is better (but feel
free to talk it here too). There are different approaches, and the
current one is not perfect but I don't see any perfect design.

Reviewers of the patch?

Thanks,

-- 
Carles Pina i Estany
	http://pinux.info

[-- Attachment #2: ChangeLog.memory --]
[-- Type: text/plain, Size: 520 bytes --]

2009-11-29  Carles Pina i Estany <carles@pina.cat>

	* gettext/gettext.c: Include `<grub/list.h>'. Define grub_gettext_msg,
	grub_gettext_msg_list.
	(grub_gettext_gettranslation_from_position): Return static const char *
	and not static char *
	(grub_gettext_translate): Add the translated strings into a list, 
	returns from the list if existing there.
	(grub_gettext_delete_list): Delete the list.
	(grub_gettext_env_write_lang): Call grub_gettext_delete_list changes
	the language.
	(GRUB_MOD_FINI): Delete the list.

[-- Attachment #3: gettext_memory.patch --]
[-- Type: text/x-diff, Size: 3355 bytes --]

=== modified file 'gettext/gettext.c'
--- gettext/gettext.c	2009-11-24 21:42:14 +0000
+++ gettext/gettext.c	2009-11-29 00:41:29 +0000
@@ -17,6 +17,7 @@
  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <grub/list.h>
 #include <grub/types.h>
 #include <grub/misc.h>
 #include <grub/mm.h>
@@ -33,7 +34,6 @@
    http://www.gnu.org/software/autoconf/manual/gettext/MO-Files.html .
 */
 
-
 static grub_file_t fd_mo;
 
 static int grub_gettext_offsetoriginal;
@@ -41,6 +41,16 @@ static int grub_gettext_max;
 
 static const char *(*grub_gettext_original) (const char *s);
 
+struct grub_gettext_msg
+{
+  struct grub_gettext_msg *next;
+  const char *name;
+
+  const char *translated;
+};
+
+struct grub_gettext_msg *grub_gettext_msg_list = NULL;
+
 #define GETTEXT_MAGIC_NUMBER 		0
 #define GETTEXT_FILE_FORMAT		4
 #define GETTEXT_NUMBER_OF_STRINGS 	8
@@ -79,7 +89,7 @@ grub_gettext_getstring_from_offset (grub
   translation[length] = '\0';
 }
 
-static char *
+static const char *
 grub_gettext_gettranslation_from_position (int position)
 {
   int offsettranslation;
@@ -130,9 +140,26 @@ static const char *
 grub_gettext_translate (const char *orig)
 {
   char *current_string;
-  char *ret;
+  const char *ret;
 
   int min, max, current;
+  int found = 0;
+
+  struct grub_gettext_msg *cur;
+
+  cur = grub_named_list_find (GRUB_AS_NAMED_LIST (grub_gettext_msg_list),
+			      orig);
+
+  if (!cur)
+    cur = grub_zalloc (sizeof (*cur));
+  else
+    return cur->translated;
+
+  if (!cur)
+    {
+      grub_errno = GRUB_ERR_NONE;
+      return orig;
+    }
 
   if (fd_mo == 0)
     return orig;
@@ -142,7 +169,7 @@ grub_gettext_translate (const char *orig
 
   current = (max + min) / 2;
 
-  while (current != min && current != max)
+  while (current != min && current != max && found == 0)
     {
       current_string = grub_gettext_getstring_from_position (current);
 
@@ -160,13 +187,26 @@ grub_gettext_translate (const char *orig
       else if (grub_strcmp (current_string, orig) == 0)
 	{
 	  grub_free (current_string);
-	  return grub_gettext_gettranslation_from_position (current);
+	  found = 1;
 	}
       current = (max + min) / 2;
     }
 
-  ret = grub_malloc (grub_strlen (orig) + 1);
-  grub_strcpy (ret, orig);
+  ret =
+    found ? grub_gettext_gettranslation_from_position (current) :
+    grub_strdup (orig);
+
+  cur->name = grub_strdup (orig);
+  if (!cur->name)
+    {
+      grub_free (cur);
+      return orig;
+    }
+
+  cur->translated = ret;
+  grub_list_push (GRUB_AS_LIST_P (&grub_gettext_msg_list),
+		  GRUB_AS_LIST (cur));
+
   return ret;
 }
 
@@ -259,12 +299,26 @@ grub_gettext_init_ext (const char *lang)
     }
 }
 
+static void
+grub_gettext_delete_list ()
+{
+  struct grub_gettext_msg *item;
+
+  while ((item =
+	  grub_list_pop (GRUB_AS_LIST_P (&grub_gettext_msg_list))) != 0)
+    {
+      // Don't delete the translated message because could be in use.
+    }
+}
+
 static char *
 grub_gettext_env_write_lang (struct grub_env_var *var
 			     __attribute__ ((unused)), const char *val)
 {
   grub_gettext_init_ext (val);
 
+  grub_gettext_delete_list ();
+
   return grub_strdup (val);
 }
 
@@ -307,5 +361,7 @@ GRUB_MOD_FINI (gettext)
   if (fd_mo != 0)
     grub_file_close (fd_mo);
 
+  grub_gettext_delete_list ();
+
   grub_gettext = grub_gettext_original;
 }

Re: gettext.c patch: reuse memory

[Robert Millan]

On Sun, Nov 29, 2009 at 12:49:50AM +0000, Carles Pina i Estany wrote:
> 
> Hello,
> 
> This week I realised of a quite big mistake in the gettext module. Every
> time that the user of this module was asking for string translation,
> gettext module was allocating new memory and returning it. So if the
> user was asking 10 times for the same string, gettext was creating 10
> new strings and leaking memory.
> 
> With the attached patch, gettext module saves in a list the
> translations.  So if a user asks again for the same translation it
> returns the same pointer to the already allocated string instead of a
> new one.
> 
> If someone wants to discuss things maybe in the IRC is better (but feel
> free to talk it here too). There are different approaches, and the
> current one is not perfect but I don't see any perfect design.

How does GNU gettext handle this?  I suspect it could be simpler.

For example, is it practical to allocate a big chunk of memory for the whole
.mo, then return pointers to it?

-- 
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."

Re: gettext.c patch: reuse memory

[Carles Pina i Estany]

Hello,

On Nov/29/2009, Robert Millan wrote:
> On Sun, Nov 29, 2009 at 12:49:50AM +0000, Carles Pina i Estany wrote:

[...]

> > With the attached patch, gettext module saves in a list the
> > translations.  So if a user asks again for the same translation it
> > returns the same pointer to the already allocated string instead of a
> > new one.

[...]

> How does GNU gettext handle this?  I suspect it could be simpler.

The part of code about is here:
http://cvs.savannah.gnu.org/viewvc/gettext/gettext-runtime/intl/dcigettext.c?revision=1.41&root=gettext&view=markup

(search for the line that contains "Since tfind/tsearch manage a
balanced tree")

I hope that I'm not mistaken: they use a balanced tree to re-use the
translations. Now we are using a list.

> For example, is it practical to allocate a big chunk of memory for the whole
> .mo, then return pointers to it?

I have thought to return a pointer to a const char* that gets reused on
the next _("XX"); (like QByteArray.data() in Qt). But this is not the
standard behaviour of gettext utils and one can have mistakes like:

const char* msg = _("hello %s");
grub_printf(_("Welcome..."));

grub_printf(msg,%user);

Where msg in the grub_printf has been already reused.

We can agree that gettext in Grub behaves in this way and force the
users to copy the strings (Solution B)

If I understood correctly Vladimir in the IRC suggested to translate on
the same char* that it's passed to _( ) (resize if needed), but I don't
like since it's not the standard behaviour and it's by definition a
const char* (for the cases that it's _("hello") , etc.)

In IRC we thought to implement the same behaviour with a hash table but
at the moment this doesn't look necessary at all and too complex for
what we need. But I'm open to keep discussing it.

I suspect that a Grub2 use will handle about 10 or 15 strings in memory.
And more strings if the user uses the Grub console, like maybe 100 or
200. The magnitude of the problem is to have 200 strings in memory that
are or are not being used. I have some functions to debug it, when I
will gettexttize more files I will the exact number.

So, the only thing that I would do is the first behaviour and force the
users the duplicate the strings. If we prefer so tell me and I will
implement it as soon as possible.

-- 
Carles Pina i Estany
	http://pinux.info

Re: gettext.c patch: reuse memory

[Carles Pina i Estany]

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


Hi,

Find attached a new version of the same patch (same approach).

Cheers,

-- 
Carles Pina i Estany
	http://pinux.info

[-- Attachment #2: ChangeLog.memory --]
[-- Type: text/plain, Size: 520 bytes --]

2009-11-29  Carles Pina i Estany <carles@pina.cat>

	* gettext/gettext.c: Include `<grub/list.h>'. Define grub_gettext_msg,
	grub_gettext_msg_list.
	(grub_gettext_gettranslation_from_position): Return static const char *
	and not static char *
	(grub_gettext_translate): Add the translated strings into a list, 
	returns from the list if existing there.
	(grub_gettext_delete_list): Delete the list.
	(grub_gettext_env_write_lang): Call grub_gettext_delete_list changes
	the language.
	(GRUB_MOD_FINI): Delete the list.

[-- Attachment #3: gettext_memory2.patch --]
[-- Type: text/x-diff, Size: 3308 bytes --]

=== modified file 'gettext/gettext.c'
--- gettext/gettext.c	2009-11-24 21:42:14 +0000
+++ gettext/gettext.c	2009-11-29 10:34:01 +0000
@@ -17,6 +17,7 @@
  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <grub/list.h>
 #include <grub/types.h>
 #include <grub/misc.h>
 #include <grub/mm.h>
@@ -33,7 +34,6 @@
    http://www.gnu.org/software/autoconf/manual/gettext/MO-Files.html .
 */
 
-
 static grub_file_t fd_mo;
 
 static int grub_gettext_offsetoriginal;
@@ -41,6 +41,16 @@ static int grub_gettext_max;
 
 static const char *(*grub_gettext_original) (const char *s);
 
+struct grub_gettext_msg
+{
+  struct grub_gettext_msg *next;
+  const char *name;
+
+  const char *translated;
+};
+
+struct grub_gettext_msg *grub_gettext_msg_list = NULL;
+
 #define GETTEXT_MAGIC_NUMBER 		0
 #define GETTEXT_FILE_FORMAT		4
 #define GETTEXT_NUMBER_OF_STRINGS 	8
@@ -79,7 +89,7 @@ grub_gettext_getstring_from_offset (grub
   translation[length] = '\0';
 }
 
-static char *
+static const char *
 grub_gettext_gettranslation_from_position (int position)
 {
   int offsettranslation;
@@ -130,9 +140,18 @@ static const char *
 grub_gettext_translate (const char *orig)
 {
   char *current_string;
-  char *ret;
+  const char *ret;
 
   int min, max, current;
+  int found = 0;
+
+  struct grub_gettext_msg *cur;
+
+  cur = grub_named_list_find (GRUB_AS_NAMED_LIST (grub_gettext_msg_list),
+			      orig);
+
+  if (cur)
+    return cur->translated;
 
   if (fd_mo == 0)
     return orig;
@@ -142,7 +161,7 @@ grub_gettext_translate (const char *orig
 
   current = (max + min) / 2;
 
-  while (current != min && current != max)
+  while (current != min && current != max && found == 0)
     {
       current_string = grub_gettext_getstring_from_position (current);
 
@@ -160,13 +179,31 @@ grub_gettext_translate (const char *orig
       else if (grub_strcmp (current_string, orig) == 0)
 	{
 	  grub_free (current_string);
-	  return grub_gettext_gettranslation_from_position (current);
+	  found = 1;
 	}
       current = (max + min) / 2;
     }
 
-  ret = grub_malloc (grub_strlen (orig) + 1);
-  grub_strcpy (ret, orig);
+  ret = found ? grub_gettext_gettranslation_from_position (current) : orig;
+
+  if (found)
+    {
+      cur = grub_zalloc (sizeof (*cur));
+
+      if (cur)
+	{
+	  cur->name = grub_strdup (orig);
+	  if (cur->name)
+	    {
+	      cur->translated = ret;
+	      grub_list_push (GRUB_AS_LIST_P (&grub_gettext_msg_list),
+			      GRUB_AS_LIST (cur));
+	    }
+	}
+      else
+	grub_errno = GRUB_ERR_NONE;
+    }
+
   return ret;
 }
 
@@ -259,12 +296,26 @@ grub_gettext_init_ext (const char *lang)
     }
 }
 
+static void
+grub_gettext_delete_list ()
+{
+  struct grub_gettext_msg *item;
+
+  while ((item =
+	  grub_list_pop (GRUB_AS_LIST_P (&grub_gettext_msg_list))) != 0)
+    {
+      // Don't delete the translated message because could be in use.
+    }
+}
+
 static char *
 grub_gettext_env_write_lang (struct grub_env_var *var
 			     __attribute__ ((unused)), const char *val)
 {
   grub_gettext_init_ext (val);
 
+  grub_gettext_delete_list ();
+
   return grub_strdup (val);
 }
 
@@ -307,5 +358,7 @@ GRUB_MOD_FINI (gettext)
   if (fd_mo != 0)
     grub_file_close (fd_mo);
 
+  grub_gettext_delete_list ();
+
   grub_gettext = grub_gettext_original;
 }

Re: gettext.c patch: reuse memory

[Carles Pina i Estany]

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


Hi,

On Nov/29/2009, Carles Pina i Estany wrote:

> Find attached a new version of the same patch (same approach).

new one. Original strings can be free-ed.

Just some numbers: if there are 1000 strings used (far too much! Grub
loader will not have so much or users will not use in the same session)
and each string is 50 characters (far too much too :-) ) strings are
usually shorter) and the translation is 50 characters the list will use
aprox. 100 KB.

(50 + 50) * 1000 / 1024 = 97.65 KB

(very rough numbers discarting 1000 pointers to next and 2000 pointers
to the original and translation strings, this would be aprox. 11.71 KB
more)

Cheers,

-- 
Carles Pina i Estany
	http://pinux.info

[-- Attachment #2: gettext_memory3.patch --]
[-- Type: text/x-diff, Size: 3413 bytes --]

=== modified file 'gettext/gettext.c'
--- gettext/gettext.c	2009-11-24 21:42:14 +0000
+++ gettext/gettext.c	2009-11-29 18:29:02 +0000
@@ -17,6 +17,7 @@
  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <grub/list.h>
 #include <grub/types.h>
 #include <grub/misc.h>
 #include <grub/mm.h>
@@ -33,7 +34,6 @@
    http://www.gnu.org/software/autoconf/manual/gettext/MO-Files.html .
 */
 
-
 static grub_file_t fd_mo;
 
 static int grub_gettext_offsetoriginal;
@@ -41,6 +41,16 @@ static int grub_gettext_max;
 
 static const char *(*grub_gettext_original) (const char *s);
 
+struct grub_gettext_msg
+{
+  struct grub_gettext_msg *next;
+  const char *name;
+
+  const char *translated;
+};
+
+struct grub_gettext_msg *grub_gettext_msg_list = NULL;
+
 #define GETTEXT_MAGIC_NUMBER 		0
 #define GETTEXT_FILE_FORMAT		4
 #define GETTEXT_NUMBER_OF_STRINGS 	8
@@ -79,7 +89,7 @@ grub_gettext_getstring_from_offset (grub
   translation[length] = '\0';
 }
 
-static char *
+static const char *
 grub_gettext_gettranslation_from_position (int position)
 {
   int offsettranslation;
@@ -130,9 +140,18 @@ static const char *
 grub_gettext_translate (const char *orig)
 {
   char *current_string;
-  char *ret;
+  const char *ret;
 
   int min, max, current;
+  int found = 0;
+
+  struct grub_gettext_msg *cur;
+
+  cur = grub_named_list_find (GRUB_AS_NAMED_LIST (grub_gettext_msg_list),
+			      orig);
+
+  if (cur)
+    return cur->translated;
 
   if (fd_mo == 0)
     return orig;
@@ -142,7 +161,7 @@ grub_gettext_translate (const char *orig
 
   current = (max + min) / 2;
 
-  while (current != min && current != max)
+  while (current != min && current != max && found == 0)
     {
       current_string = grub_gettext_getstring_from_position (current);
 
@@ -160,13 +179,31 @@ grub_gettext_translate (const char *orig
       else if (grub_strcmp (current_string, orig) == 0)
 	{
 	  grub_free (current_string);
-	  return grub_gettext_gettranslation_from_position (current);
+	  found = 1;
 	}
       current = (max + min) / 2;
     }
 
-  ret = grub_malloc (grub_strlen (orig) + 1);
-  grub_strcpy (ret, orig);
+  ret = found ? grub_gettext_gettranslation_from_position (current) : orig;
+
+  if (found)
+    {
+      cur = grub_zalloc (sizeof (*cur));
+
+      if (cur)
+	{
+	  cur->name = grub_strdup (orig);
+	  if (cur->name)
+	    {
+	      cur->translated = ret;
+	      grub_list_push (GRUB_AS_LIST_P (&grub_gettext_msg_list),
+			      GRUB_AS_LIST (cur));
+	    }
+	}
+      else
+	grub_errno = GRUB_ERR_NONE;
+    }
+
   return ret;
 }
 
@@ -259,12 +296,29 @@ grub_gettext_init_ext (const char *lang)
     }
 }
 
+static void
+grub_gettext_delete_list ()
+{
+  struct grub_gettext_msg *item;
+
+  while ((item =
+	  grub_list_pop (GRUB_AS_LIST_P (&grub_gettext_msg_list))) != 0)
+    {
+      char* original = (char*) ((struct grub_gettext_msg *) item)->name;
+      grub_free (original);
+
+      // Don't delete the translated message because could be in use.
+    }
+}
+
 static char *
 grub_gettext_env_write_lang (struct grub_env_var *var
 			     __attribute__ ((unused)), const char *val)
 {
   grub_gettext_init_ext (val);
 
+  grub_gettext_delete_list ();
+
   return grub_strdup (val);
 }
 
@@ -307,5 +361,7 @@ GRUB_MOD_FINI (gettext)
   if (fd_mo != 0)
     grub_file_close (fd_mo);
 
+  grub_gettext_delete_list ();
+
   grub_gettext = grub_gettext_original;
 }


[-- Attachment #3: ChangeLog.memory --]
[-- Type: text/plain, Size: 520 bytes --]

2009-11-29  Carles Pina i Estany <carles@pina.cat>

	* gettext/gettext.c: Include `<grub/list.h>'. Define grub_gettext_msg,
	grub_gettext_msg_list.
	(grub_gettext_gettranslation_from_position): Return static const char *
	and not static char *
	(grub_gettext_translate): Add the translated strings into a list, 
	returns from the list if existing there.
	(grub_gettext_delete_list): Delete the list.
	(grub_gettext_env_write_lang): Call grub_gettext_delete_list changes
	the language.
	(GRUB_MOD_FINI): Delete the list.

Re: gettext.c patch: reuse memory

[Carles Pina i Estany]

Hi,

On Nov/29/2009, Carles Pina i Estany wrote:

> Just some numbers: if there are 1000 strings used (far too much! Grub
> loader will not have so much or users will not use in the same session)
> and each string is 50 characters (far too much too :-) ) strings are
> usually shorter) and the translation is 50 characters the list will use
> aprox. 100 KB.
> 
> (50 + 50) * 1000 / 1024 = 97.65 KB

I think that this is more like (7 + 7) * 60 = 840 bytes, less than 1 KB.

One approach is that we use the list for now and I prepare a benchmark
code (it's very easy). When more things are translated we can reconsider
it with some numbers and not "guesses" and "I think".

-- 
Carles Pina i Estany
	http://pinux.info