Skip to contentSkip to conversation

dynamic cache allocation

PATCH In review phcoder 3 participants 6 messages Mar 7, 2009 – Mar 9, 2009

lore
Share & tools
lore

phcoder

author
#0 lore raw

PATCH 1/1 dynamic cache allocation

Hello. Discussing with Robert Millan and Bean on IRC we noticed that disk cache index is statically allocated. Here is a proposal to change it to dynamic allocation proportional to the size of available memory.

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
disk.c +37 -4
Index: kern/disk.c
===================================================================
@@ -41,7 +41,8 @@ struct grub_disk_cache
   int lock;
 };
 
-static struct grub_disk_cache grub_disk_cache_table[GRUB_DISK_CACHE_NUM];
+static struct grub_disk_cache *grub_disk_cache_table = 0;
+static int grub_disk_cache_num = 0;
 
 void (*grub_disk_firmware_fini) (void);
 int grub_disk_firmware_is_tainted;
@@ -68,7 +69,7 @@ grub_disk_cache_get_index (unsigned long dev_id, u
 {
   return ((dev_id * 524287UL + disk_id * 2606459UL
 	   + ((unsigned) (sector >> GRUB_DISK_CACHE_BITS)))
-	  % GRUB_DISK_CACHE_NUM);
+	  % grub_disk_cache_num);
 }
 
 static void
@@ -78,6 +79,9 @@ grub_disk_cache_invalidate (unsigned long dev_id,
   unsigned index;
   struct grub_disk_cache *cache;
 
+  if (!grub_disk_cache_table)
+    return;
+
   sector &= ~(GRUB_DISK_CACHE_SIZE - 1);
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
@@ -97,7 +101,10 @@ grub_disk_cache_invalidate_all (void)
 {
   unsigned i;
 
-  for (i = 0; i < GRUB_DISK_CACHE_NUM; i++)
+  if (!grub_disk_cache_table)
+    return;
+
+  for (i = 0; i < grub_disk_cache_num; i++)
     {
       struct grub_disk_cache *cache = grub_disk_cache_table + i;
 
@@ -116,6 +123,14 @@ grub_disk_cache_fetch (unsigned long dev_id, unsig
   struct grub_disk_cache *cache;
   unsigned index;
 
+  if (!grub_disk_cache_table)
+    {
+#if 0
+      grub_disk_cache_misses++;
+#endif
+      return 0;
+    }
+
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
 
@@ -143,6 +158,9 @@ grub_disk_cache_unlock (unsigned long dev_id, unsi
   struct grub_disk_cache *cache;
   unsigned index;
 
+  if (!grub_disk_cache_table)
+    return ;
+
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
 
@@ -157,7 +175,22 @@ grub_disk_cache_store (unsigned long dev_id, unsig
 {
   unsigned index;
   struct grub_disk_cache *cache;
-  
+
+  if (!grub_disk_cache_table)
+    {
+#ifdef GRUB_UTIL
+      grub_disk_cache_num = GRUB_UTIL_CACHE_NUM;
+#else
+      grub_disk_cache_num = grub_mm_get_free ()  / GRUB_DISK_CACHE_DIVIDE;
+#endif
+      grub_disk_cache_table = (struct grub_disk_cache *)
+	grub_malloc (grub_disk_cache_num * sizeof (struct grub_disk_cache));
+    }
+
+  if (!grub_disk_cache_table)
+    return grub_error (GRUB_ERR_OUT_OF_MEMORY, 
+		       "couldn't allocate space for cache index");
+
   grub_disk_cache_invalidate (dev_id, disk_id, sector);
   
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
mm.c +27 -0
Index: kern/mm.c
===================================================================
@@ -449,6 +449,33 @@ grub_realloc (void *ptr, grub_size_t size)
   return q;
 }
 
+grub_size_t
+grub_mm_get_free (void)
+{
+  grub_mm_region_t r;
+  grub_size_t ret = 0;
+
+  for (r = base; r; r = r->next)
+    {
+      grub_mm_header_t p;
+
+      /* Follow the free list.  */
+      p = r->first;
+      do
+	{
+	  if (p->magic != GRUB_MM_FREE_MAGIC)
+	    grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
+
+	  ret += p->size << GRUB_MM_ALIGN_LOG2;
+	  p = p->next;
+	}
+      while (p != r->first);
+    }
+
+  return ret;
+}
+
+
 #ifdef MM_DEBUG
 int grub_mm_debug = 0;
 
grub/disk.h +7 -2
Index: include/grub/disk.h
===================================================================
@@ -129,9 +129,14 @@ typedef struct grub_disk_memberlist *grub_disk_mem
 #define GRUB_DISK_SECTOR_SIZE	0x200
 #define GRUB_DISK_SECTOR_BITS	9
 
-/* The maximum number of disk caches.  */
-#define GRUB_DISK_CACHE_NUM	1021
+/* Allocate one cache entry per N bytes. 
+   By default use up to one quarter of memory available for allocation  */
+#define GRUB_DISK_CACHE_DIVIDE	16536
 
+/* On grub-util we can't know the available memory size and since host OS 
+   already caches data we don't need a big cache*/
+#define GRUB_UTIL_CACHE_NUM 100
+
 /* The size of a disk cache in sector units.  */
 #define GRUB_DISK_CACHE_SIZE	8
 #define GRUB_DISK_CACHE_BITS	3
grub/mm.h +1 -0
Index: include/grub/mm.h
===================================================================
@@ -33,6 +33,7 @@ void *EXPORT_FUNC(grub_malloc) (grub_size_t size);
 void EXPORT_FUNC(grub_free) (void *ptr);
 void *EXPORT_FUNC(grub_realloc) (void *ptr, grub_size_t size);
 void *EXPORT_FUNC(grub_memalign) (grub_size_t align, grub_size_t size);
+grub_size_t EXPORT_FUNC(grub_mm_get_free) (void);
 
 /* For debugging.  */
 #if defined(MM_DEBUG) && !defined(GRUB_UTIL)
ChangeLog +14 -0
Index: ChangeLog
===================================================================
@@ -1,3 +1,17 @@
+2009-03-07  Vladimir Serbinenko  <[email protected]>
+
+	Dynamic cache allocation
+
+	* kern/disk.c (grub_disk_cache_table): changed declaration as pointer 
+	instead of array. All users updated
+	* include/grub/disk.h (GRUB_DISK_CACHE_NUM): changed to ...
+	(grub_disk_cache_num): ... a variable. All users updated
+	* kern/disk.c (grub_disk_cache_store): allocate cache index
+	* kern/mm.c (grub_mm_get_free): new function
+	* include/grub/disk.h (GRUB_DISK_CACHE_DIVIDE): new declaration
+	(GRUB_UTIL_CACHE_NUM): likewise
+	* include/grub/mm.h (grub_mm_get_free): likewise
+
 2009-03-07  Bean  <[email protected]>
 
 	* loader/i386/efi/linux.c (grub_rescue_cmd_initrd): Fix a bug in initrd
#1 lore raw

disk.c grub_disk_cache_store (unsigned long dev_id, unsig

Quoted 5 lines · phcoder
disk.c +4 -0
+      grub_disk_cache_table = (struct grub_disk_cache *)
+	grub_malloc (grub_disk_cache_num * sizeof (struct grub_disk_cache));
[...]
+   By default use up to one quarter of memory available for allocation  */
+#define GRUB_DISK_CACHE_DIVIDE	16536

I might be missing something, but I think this implies our cache will stop working if the memory map doesn't include a contigous block that is as big as one quarter of total memory.

I think we should be more conservative and define an upper bound for how big our cache is supposed to be in a normal use case. In most cases, we'll have as much memory available as we need for this purpose, and it's only a few situations (i.e. machines with very low memory) that might be a problem.

Thoughts?

Signature · 5 lines
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."
author
#2 lore raw
Quoted 11 lines · Robert Millan

disk.c grub_disk_cache_store (unsigned long dev_id, unsig

Quoted 5 lines · phcoder
disk.c +4 -0
+      grub_disk_cache_table = (struct grub_disk_cache *)
+	grub_malloc (grub_disk_cache_num * sizeof (struct grub_disk_cache));
[...]
+   By default use up to one quarter of memory available for allocation  */
+#define GRUB_DISK_CACHE_DIVIDE	16536

I might be missing something, but I think this implies our cache will stop working if the memory map doesn't include a contigous block that is as big as one quarter of total memory.

It uses the indirection. The space that is allocated by this code is only for the cache index. Every index entry is 20 bytes and describes a cache entry of 4096 bytes. So for cache to work we need just a block of size of 1/800 of free allocatable memory (not the total memory but only the memory which was announced to mm.c as free). On the BIOS system with 3GB only 1/4 of available memory is announced as free (it's probably different with Vesa's new allocator). It means that cache index will take about 1MiB (about 4MiB if Vesa's allocator uses memory better)

Quoted 7 lines

I think we should be more conservative and define an upper bound for how big our cache is supposed to be in a normal use case. In most cases, we'll have as much memory available as we need for this purpose, and it's only a few situations (i.e. machines with very low memory) that might be a problem.

Thoughts?

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
#3 lore raw
In reply to phcoder
Quoted 3 lines · phcoder

Hello. Discussing with Robert Millan and Bean on IRC we noticed that disk cache index is statically allocated. Here is a proposal to change it to dynamic allocation proportional to the size of available memory.

And the gain is ?

author
#4 lore raw
Quoted 6 lines · Vesa Jääskeläinen
Quoted 3 lines · phcoder

Hello. Discussing with Robert Millan and Bean on IRC we noticed that disk cache index is statically allocated. Here is a proposal to change it to dynamic allocation proportional to the size of available memory.

And the gain is ?

Faster booting if extensive directory scanning is needed to load OS (applies to xnu)

Quoted 6 lines

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
author
#5 lore raw

Update to the patch

Quoted 17 lines · phcoder
Quoted 6 lines · Vesa Jääskeläinen
Quoted 3 lines · phcoder

Hello. Discussing with Robert Millan and Bean on IRC we noticed that disk cache index is statically allocated. Here is a proposal to change it to dynamic allocation proportional to the size of available memory.

And the gain is ?

Faster booting if extensive directory scanning is needed to load OS (applies to xnu)

Quoted 6 lines

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
disk.c +39 -4
Index: kern/disk.c
===================================================================
@@ -41,7 +41,8 @@ struct grub_disk_cache
   int lock;
 };
 
-static struct grub_disk_cache grub_disk_cache_table[GRUB_DISK_CACHE_NUM];
+static struct grub_disk_cache *grub_disk_cache_table = 0;
+static int grub_disk_cache_num = 0;
 
 void (*grub_disk_firmware_fini) (void);
 int grub_disk_firmware_is_tainted;
@@ -68,7 +69,7 @@ grub_disk_cache_get_index (unsigned long dev_id, u
 {
   return ((dev_id * 524287UL + disk_id * 2606459UL
 	   + ((unsigned) (sector >> GRUB_DISK_CACHE_BITS)))
-	  % GRUB_DISK_CACHE_NUM);
+	  % grub_disk_cache_num);
 }
 
 static void
@@ -78,6 +79,9 @@ grub_disk_cache_invalidate (unsigned long dev_id,
   unsigned index;
   struct grub_disk_cache *cache;
 
+  if (!grub_disk_cache_table)
+    return;
+
   sector &= ~(GRUB_DISK_CACHE_SIZE - 1);
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
@@ -97,7 +101,10 @@ grub_disk_cache_invalidate_all (void)
 {
   unsigned i;
 
-  for (i = 0; i < GRUB_DISK_CACHE_NUM; i++)
+  if (!grub_disk_cache_table)
+    return;
+
+  for (i = 0; i < grub_disk_cache_num; i++)
     {
       struct grub_disk_cache *cache = grub_disk_cache_table + i;
 
@@ -116,6 +123,14 @@ grub_disk_cache_fetch (unsigned long dev_id, unsig
   struct grub_disk_cache *cache;
   unsigned index;
 
+  if (!grub_disk_cache_table)
+    {
+#if 0
+      grub_disk_cache_misses++;
+#endif
+      return 0;
+    }
+
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
 
@@ -143,6 +158,9 @@ grub_disk_cache_unlock (unsigned long dev_id, unsi
   struct grub_disk_cache *cache;
   unsigned index;
 
+  if (!grub_disk_cache_table)
+    return ;
+
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
   cache = grub_disk_cache_table + index;
 
@@ -157,7 +175,24 @@ grub_disk_cache_store (unsigned long dev_id, unsig
 {
   unsigned index;
   struct grub_disk_cache *cache;
-  
+
+  if (!grub_disk_cache_table)
+    {
+#ifdef GRUB_UTIL
+      grub_disk_cache_num = GRUB_UTIL_CACHE_NUM;
+#else
+      grub_disk_cache_num = grub_mm_get_free ()  / GRUB_DISK_CACHE_DIVIDE;
+#endif
+      grub_disk_cache_table = (struct grub_disk_cache *)
+	grub_malloc (grub_disk_cache_num * sizeof (struct grub_disk_cache));
+      grub_memset (grub_disk_cache_table, 0,
+		   grub_disk_cache_num * sizeof (struct grub_disk_cache));
+    }
+
+  if (!grub_disk_cache_table)
+    return grub_error (GRUB_ERR_OUT_OF_MEMORY, 
+		       "couldn't allocate space for cache index");
+
   grub_disk_cache_invalidate (dev_id, disk_id, sector);
   
   index = grub_disk_cache_get_index (dev_id, disk_id, sector);
mm.c +27 -0
Index: kern/mm.c
===================================================================
@@ -449,6 +449,33 @@ grub_realloc (void *ptr, grub_size_t size)
   return q;
 }
 
+grub_size_t
+grub_mm_get_free (void)
+{
+  grub_mm_region_t r;
+  grub_size_t ret = 0;
+
+  for (r = base; r; r = r->next)
+    {
+      grub_mm_header_t p;
+
+      /* Follow the free list.  */
+      p = r->first;
+      do
+	{
+	  if (p->magic != GRUB_MM_FREE_MAGIC)
+	    grub_fatal ("free magic is broken at %p: 0x%x", p, p->magic);
+
+	  ret += p->size << GRUB_MM_ALIGN_LOG2;
+	  p = p->next;
+	}
+      while (p != r->first);
+    }
+
+  return ret;
+}
+
+
 #ifdef MM_DEBUG
 int grub_mm_debug = 0;
 
grub/disk.h +7 -2
Index: include/grub/disk.h
===================================================================
@@ -129,9 +129,14 @@ typedef struct grub_disk_memberlist *grub_disk_mem
 #define GRUB_DISK_SECTOR_SIZE	0x200
 #define GRUB_DISK_SECTOR_BITS	9
 
-/* The maximum number of disk caches.  */
-#define GRUB_DISK_CACHE_NUM	1021
+/* Allocate one cache entry per N bytes. 
+   By default use up to one quarter of memory available for allocation  */
+#define GRUB_DISK_CACHE_DIVIDE	16536
 
+/* On grub-util we can't know the available memory size and since host OS 
+   already caches data we don't need a big cache*/
+#define GRUB_UTIL_CACHE_NUM 100
+
 /* The size of a disk cache in sector units.  */
 #define GRUB_DISK_CACHE_SIZE	8
 #define GRUB_DISK_CACHE_BITS	3
grub/mm.h +1 -0
Index: include/grub/mm.h
===================================================================
@@ -33,6 +33,7 @@ void *EXPORT_FUNC(grub_malloc) (grub_size_t size);
 void EXPORT_FUNC(grub_free) (void *ptr);
 void *EXPORT_FUNC(grub_realloc) (void *ptr, grub_size_t size);
 void *EXPORT_FUNC(grub_memalign) (grub_size_t align, grub_size_t size);
+grub_size_t EXPORT_FUNC(grub_mm_get_free) (void);
 
 /* For debugging.  */
 #if defined(MM_DEBUG) && !defined(GRUB_UTIL)
ChangeLog +14 -0
Index: ChangeLog
===================================================================
@@ -1,3 +1,17 @@
+2009-03-07  Vladimir Serbinenko  <[email protected]>
+
+	Dynamic cache allocation
+
+	* kern/disk.c (grub_disk_cache_table): changed declaration as pointer 
+	instead of array. All users updated
+	* include/grub/disk.h (GRUB_DISK_CACHE_NUM): changed to ...
+	(grub_disk_cache_num): ... a variable. All users updated
+	* kern/disk.c (grub_disk_cache_store): allocate cache index
+	* kern/mm.c (grub_mm_get_free): new function
+	* include/grub/disk.h (GRUB_DISK_CACHE_DIVIDE): new declaration
+	(GRUB_UTIL_CACHE_NUM): likewise
+	* include/grub/mm.h (grub_mm_get_free): likewise
+
 2009-03-07  Bean  <[email protected]>
 
 	* loader/i386/efi/linux.c (grub_rescue_cmd_initrd): Fix a bug in initrd