Major rewrite of the machinery which keeps track of segments:
* remove initialisation-time circularities by not using the
skiplist mechanism and therefore not using any dynamically
allocated memory in support of this mechanism
* Add comments about how it works (it is pretty opaque) so as
to help future maintainers/bug-fixers
It only just works and many things are still broken. That should
improve rapidly however.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@3242 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/coregrind/vg_memory.c b/coregrind/vg_memory.c
index f4fb1a9..ebfd51a 100644
--- a/coregrind/vg_memory.c
+++ b/coregrind/vg_memory.c
@@ -35,7 +35,219 @@
/* Define to debug the memory-leak-detector. */
/* #define VG_DEBUG_LEAKCHECK */
-static const Bool mem_debug = False;
+static const Bool mem_debug = True; //False;
+
+/*--------------------------------------------------------------*/
+/*--- ---*/
+/*--------------------------------------------------------------*/
+
+#define VG_N_SEGMENTS 400
+
+/* Array [0 .. segments_used-1] of all mappings. */
+/* Sorted by .addr field. */
+/* I: len may not be zero. */
+/* I: overlapping segments are not allowed. */
+
+static Segment segments[VG_N_SEGMENTS];
+static Int segments_used = 0;
+
+
+/* Returns -1 if 'a' denotes an address prior to seg, 1 if it denotes
+ an address after it, and 0 if it denotes an address covered by
+ seg. */
+static Int compare_addr_with_seg ( Addr a, Segment* seg )
+{
+ if (a < seg->addr)
+ return -1;
+ if (a >= seg->addr + seg->len)
+ return 1;
+ return 0;
+}
+
+/* Find the (index of the) segment that contains 'a', or -1 if
+ none. */
+static Int find_segment ( Addr a )
+{
+ Int i;
+ for (i = 0; i < segments_used; i++) {
+ if (compare_addr_with_seg(a, &segments[i]) == 0)
+ return i;
+ }
+ return -1;
+}
+
+
+/* Assumes that 'a' is not in any segment. Finds the index of the
+ lowest-addressed segment above 'a', or -1 if none. Passing 'a'
+ which is in fact in a segment is a checked error.
+*/
+static Int find_segment_above_unmapped ( Addr a )
+{
+ Int i, r;
+ for (i = 0; i < segments_used; i++) {
+ r = compare_addr_with_seg(a, &segments[i]);
+ vg_assert(r != 0); /* 'a' should not be in any segment. */
+ if (r == 1)
+ continue;
+ vg_assert(r == -1);
+ break;
+ }
+
+ if (i == segments_used)
+ return -1; /* not found */
+ else
+ return i;
+}
+
+
+/* Assumes that 'a' is in some segment. Finds the next segment along,
+ or NULL if none. Passing 'a' which is in fact not in a segment is
+ a checked error.
+*/
+static Int find_segment_above_mapped ( Addr a )
+{
+ Int i, r;
+ for (i = 0; i < segments_used; i++) {
+ r = compare_addr_with_seg(a, &segments[i]);
+ if (r == 1)
+ continue; /* not yet there */
+ if (r == 0)
+ break; /* found it */
+ vg_assert(0);
+ /* we shouldn't get here -- r == -1 and so it means we went past
+ 'a' without seeing it -- it is therefore unmapped. */
+ /*NOTREACHED*/
+ }
+
+ vg_assert(i < segments_used);
+ if (i == segments_used-1)
+ return -1; /* not found */
+ else
+ return i+1;
+}
+
+
+/* Shift segments[i .. segments_used-1] up by one. */
+static void make_space_at ( Int i )
+{
+ Int j;
+ vg_assert(i >= 0 && i <= segments_used);
+ vg_assert(segments_used >= 0);
+ vg_assert(segments_used+1 < VG_N_SEGMENTS);
+ for (j = segments_used; j > i; j--)
+ segments[j] = segments[j-1];
+ segments_used++;
+}
+
+/* Shift segments [i+1 .. segments_used-1] down by one, and decrement
+ segments_used. */
+static void delete_segment_at ( Int i )
+{
+ Int j;
+ vg_assert(i >= 0 && i < segments_used);
+ for (j = i+1; j < segments_used; j++)
+ segments[j-1] = segments[j];
+ segments_used--;
+ vg_assert(segments_used >= 0 && segments_used < VG_N_SEGMENTS);
+}
+
+
+/* Fill the i'th record all with zeroes. */
+static void zeroise_segment ( Int i )
+{
+ vg_assert(i >= 0 && i < segments_used);
+ segments[i].prot = 0;
+ segments[i].flags = 0;
+ segments[i].addr = 0;
+ segments[i].len = 0;
+ segments[i].offset = 0;
+ segments[i].filename = NULL;
+ segments[i].dev = 0;
+ segments[i].ino = 0;
+ segments[i].symtab = NULL;
+}
+
+/* Create a segment to contain 'a', and return its index. Or -1 if
+ this failed because some other segment already contains 'a'. If
+ successful, fill in the segment's .addr field with 'a' but leave
+ all other fields alone.
+*/
+static Int create_segment ( Addr a )
+{
+ Int i, r;
+ for (i = 0; i < segments_used; i++) {
+ r = compare_addr_with_seg( a, &segments[i] );
+ if (r == 1)
+ continue; /* seg[i] precedes a */
+ if (r == 0)
+ return -1; /* seg[i] contains a. Give up */
+ vg_assert(r == -1);
+ break;
+ }
+ /* a precedes seg[i]. Shift segs at i and above up one, and use
+ this slot. */
+ make_space_at(i);
+ zeroise_segment(i);
+ segments[i].addr = a;
+ return i;
+}
+
+//static
+void show_segments ( HChar* who )
+{
+ Int i;
+ VG_(printf)("<<< SHOW_SEGMENTS: %s %d\n", who, segments_used);
+ for (i = 0; i < segments_used; i++) {
+ VG_(printf)(
+ "%2d: %p %llu 0x%x 0x%x 0x%x %d %lld %s\n",
+ i,
+ segments[i].addr, (ULong)segments[i].len, segments[i].prot, segments[i].flags, segments[i].dev, segments[i].ino, (Long)segments[i].offset, "qqq" /*segments[i].filename*/);
+}
+ VG_(printf)(">>>\n");
+}
+
+/* Find the segment containing 'a' and split it into two pieces at
+ 'a'. Does nothing if no segment contains 'a', or if the split
+ would cause either of the pieces to have zero size.
+
+ If 'a' is not found, or if no splitting happens, -1 is returned.
+
+ If a value 'r' other than -1 is returned, this is the index of the
+ higher-addressed segment resulting from the split, and the index of
+ the lower-addressed segment is r-1.
+*/
+static Int split_segment ( Addr a )
+{
+ Int r;
+ HWord delta;
+ vg_assert((a & (VKI_PAGE_SIZE-1)) == 0);
+ r = find_segment(a);
+ if (r == -1)
+ /* not found */
+ return -1;
+ if (segments[r].addr == a)
+ /* segment starts at 'a', so splitting it would create a
+ zero-sized segment */
+ return -1;
+
+ /* copy original; make adjustments. */
+ vg_assert(a > segments[r].addr);
+ delta = a - segments[r].addr;
+ make_space_at(r);
+ segments[r] = segments[r+1];
+ segments[r].len = delta;
+ segments[r+1].len -= delta;
+ segments[r+1].addr += delta;
+ segments[r+1].offset += delta;
+ return r+1;
+}
+
+/*--------------------------------------------------------------*/
+/*--- ---*/
+/*--------------------------------------------------------------*/
+
+#define IS_PAGE_ALIGNED(_aa) (((_aa) & (VKI_PAGE_SIZE-1)) == 0)
+
static Int addrcmp(const void *ap, const void *bp)
{
@@ -70,7 +282,6 @@
{
Addr se = s->addr+s->len;
Addr pe = p+len;
-
vg_assert(pe >= p);
return (p >= s->addr && pe <= se);
@@ -80,7 +291,6 @@
{
Addr se = s->addr+s->len;
Addr pe = p+len;
-
vg_assert(pe >= p);
return (p < se && pe > s->addr);
@@ -118,7 +328,7 @@
Segment *s = VG_(SkipList_Find)(&sk_segments, &a);
Segment *ns;
Int delta;
-
+vg_assert(0);
vg_assert((a & (VKI_PAGE_SIZE-1)) == 0);
/* missed */
@@ -159,45 +369,41 @@
Segment *s;
Segment *next;
static const Bool debug = False || mem_debug;
- Addr end;
+ Addr end, s_end;
+ Int i;
if (len == 0)
return;
len = PGROUNDUP(len);
- vg_assert(addr == PGROUNDDN(addr));
if (debug)
VG_(printf)("unmap_range(%p, %d)\n", addr, len);
-
+ if (0) show_segments("unmap_range");
end = addr+len;
/* Everything must be page-aligned */
- vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
- vg_assert((len & (VKI_PAGE_SIZE-1)) == 0);
+ vg_assert(IS_PAGE_ALIGNED(addr));
+ vg_assert(IS_PAGE_ALIGNED(len));
- for(s = VG_(SkipList_Find)(&sk_segments, &addr);
- s != NULL && s->addr < (addr+len);
- s = next) {
- Addr seg_end = s->addr + s->len;
+ for (i = 0; i < segments_used; i++) {
+ s = &segments[i];
+ s_end = s->addr + s->len;
- /* fetch next now in case we end up deleting this segment */
- next = VG_(SkipNode_Next)(&sk_segments, s);
-
- if (debug)
+ if (0 && debug)
VG_(printf)("unmap: addr=%p-%p s=%p ->addr=%p-%p len=%d\n",
- addr, end, s, s->addr, seg_end, s->len);
+ addr, end, s, s->addr, s_end, s->len);
if (!VG_(seg_overlaps)(s, addr, len)) {
- if (debug)
+ if (0 && debug)
VG_(printf)(" (no overlap)\n");
continue;
}
/* 4 cases: */
if (addr > s->addr &&
- addr < seg_end &&
- end >= seg_end) {
+ addr < s_end &&
+ end >= s_end) {
/* this segment's tail is truncated by [addr, addr+len)
-> truncate tail
*/
@@ -205,11 +411,11 @@
if (debug)
VG_(printf)(" case 1: s->len=%d\n", s->len);
- } else if (addr <= s->addr && end > s->addr && end < seg_end) {
+ } else if (addr <= s->addr && end > s->addr && end < s_end) {
/* this segment's head is truncated by [addr, addr+len)
-> truncate head
*/
- Int delta = end - s->addr;
+ Word delta = end - s->addr;
if (debug)
VG_(printf)(" case 2: s->addr=%p s->len=%d delta=%d\n", s->addr, s->len, delta);
@@ -219,36 +425,31 @@
s->len -= delta;
vg_assert(s->len != 0);
- } else if (addr <= s->addr && end >= seg_end) {
+ } else if (addr <= s->addr && end >= s_end) {
/* this segment is completely contained within [addr, addr+len)
-> delete segment
*/
- Segment *rs = VG_(SkipList_Remove)(&sk_segments, &s->addr);
- vg_assert(rs == s);
- freeseg(s);
+ delete_segment_at(i);
if (debug)
- VG_(printf)(" case 3: s==%p deleted\n", s);
- } else if (addr > s->addr && end < seg_end) {
+ VG_(printf)(" case 3: seg %d deleted\n", i);
+ } else if (addr > s->addr && end < s_end) {
/* [addr, addr+len) is contained within a single segment
-> split segment into 3, delete middle portion
*/
- Segment *middle, *rs;
+ Int i_middle = split_segment(addr);
+ vg_assert(i_middle != -1);
+ (void)split_segment(addr+len);
- middle = VG_(split_segment)(addr);
- VG_(split_segment)(addr+len);
-
- vg_assert(middle->addr == addr);
- rs = VG_(SkipList_Remove)(&sk_segments, &addr);
- vg_assert(rs == middle);
-
- freeseg(rs);
+ vg_assert(segments[i_middle].addr == addr);
+ delete_segment_at(i_middle);
if (debug)
VG_(printf)(" case 4: subrange %p-%p deleted\n",
addr, addr+len);
}
}
+ if (0) show_segments("unmap_range(AFTER)");
}
/* Return true if two segments are adjacent and mergable (s1 is
@@ -314,21 +515,54 @@
}
}
-void VG_(map_file_segment)(Addr addr, SizeT len, UInt prot, UInt flags,
- UInt dev, UInt ino, ULong off, const Char *filename)
+
+/* Add a binding of [addr,addr+len) to
+ (prot,flags,dev,ino,off,filename) in the segment array.
+ Delete/truncate any previous mapping(s) covering that range.
+*/
+void
+VG_(map_file_segment)( Addr addr, SizeT len,
+ UInt prot, UInt flags,
+ UInt dev, UInt ino, ULong off,
+ const Char *filename)
{
Segment *s;
static const Bool debug = False || mem_debug;
Bool recycled;
+ Int idx;
if (debug)
- VG_(printf)("map_file_segment(%p, %llu, %x, %x, %4x, %d, %ld, %s)\n",
- addr, (ULong)len, prot, flags, dev, ino, off, filename);
+ VG_(printf)(
+ "\n"
+ "map_file_segment(addr=%p len=%llu prot=0x%x flags=0x%x\n"
+ " dev=0x%4x ino=%d off=%ld\n"
+ " filename='%s')\n",
+ addr, (ULong)len, prot, flags, dev, ino, off, filename);
/* Everything must be page-aligned */
- vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
+ vg_assert(IS_PAGE_ALIGNED(addr));
len = PGROUNDUP(len);
+ /* Nuke/truncate any existing segment(s) covering [addr,addr+len) */
+ VG_(unmap_range)(addr, len);
+
+ /* and now install this one */
+ idx = create_segment(addr);
+ vg_assert(segments_used >= 0 && segments_used <= VG_N_SEGMENTS);
+ vg_assert(idx != -1);
+ vg_assert(idx >= 0 && idx < segments_used);
+ vg_assert(segments[idx].addr == addr);
+ segments[idx].prot = prot;
+ segments[idx].flags = flags;
+ segments[idx].len = len;
+ segments[idx].offset = off;
+ segments[idx].filename = filename;
+ segments[idx].dev = dev;
+ segments[idx].ino = ino;
+ segments[idx].symtab = NULL;
+ return;
+
+#if 0
/* First look to see what already exists around here */
s = VG_(SkipList_Find)(&sk_segments, &addr);
@@ -419,6 +653,7 @@
/* clean up */
merge_segments(addr, len);
+#endif
}
void VG_(map_fd_segment)(Addr addr, SizeT len, UInt prot, UInt flags,
@@ -426,6 +661,7 @@
{
struct vki_stat st;
Char *name = NULL;
+ //vg_assert(0);
st.st_dev = 0;
st.st_ino = 0;
@@ -437,8 +673,8 @@
flags &= ~SF_FILE;
}
- if ((flags & SF_FILE) && filename == NULL && fd != -1)
- name = VG_(resolve_filename)(fd);
+ // if ((flags & SF_FILE) && filename == NULL && fd != -1)
+ // name = VG_(resolve_filename)(fd);
if (filename == NULL)
filename = name;
@@ -459,19 +695,29 @@
/* set new protection flags on an address range */
void VG_(mprotect_range)(Addr a, SizeT len, UInt prot)
{
+ Int r;
Segment *s, *next;
static const Bool debug = False || mem_debug;
if (debug)
- VG_(printf)("mprotect_range(%p, %d, %x)\n", a, len, prot);
+ VG_(printf)("\nmprotect_range(%p, %d, %x)\n", a, len, prot);
+ show_segments( "mprotect_range(before)" );
/* Everything must be page-aligned */
vg_assert((a & (VKI_PAGE_SIZE-1)) == 0);
len = PGROUNDUP(len);
- VG_(split_segment)(a);
- VG_(split_segment)(a+len);
+ /*VG_*/ (split_segment)(a);
+ /*VG_*/ (split_segment)(a+len);
+ r = find_segment(a);
+ vg_assert(r != -1);
+ segments[r].prot = prot;
+ show_segments( "mprotect_range(after)");
+
+ return;
+
+vg_assert(0);
for(s = VG_(SkipList_Find)(&sk_segments, &a);
s != NULL && s->addr < a+len;
s = next)
@@ -486,6 +732,11 @@
merge_segments(a, len);
}
+/* Try to find a map space for [addr,addr+len). If addr==0, it means
+ the caller is prepared to accept a space at any location; if not,
+ we will try for addr, but fail if we can't get it. This mimics
+ mmap fixed vs mmap not-fixed.
+*/
Addr VG_(find_map_space)(Addr addr, SizeT len, Bool for_client)
{
static const Bool debug = False || mem_debug;
@@ -493,15 +744,20 @@
Addr ret;
Addr limit = (for_client ? VG_(client_end)-1 : VG_(valgrind_last));
Addr base = (for_client ? VG_(client_mapbase) : VG_(valgrind_base));
+ Addr hole_start, hole_end, hstart_any, hstart_fixed, hstart_final;
+ Int i, i_any, i_fixed, i_final;
+ SizeT hole_len;
- if (addr == 0)
- addr = base;
- else {
+ Bool fixed;
+
+ if (addr == 0) {
+ fixed = False;
+ } else {
+ fixed = True;
/* leave space for redzone and still try to get the exact
- address asked for */
+ address asked for */
addr -= VKI_PAGE_SIZE;
}
- ret = addr;
/* Everything must be page-aligned */
vg_assert((addr & (VKI_PAGE_SIZE-1)) == 0);
@@ -509,6 +765,93 @@
len += VKI_PAGE_SIZE * 2; /* leave redzone gaps before and after mapping */
+ /* Scan the segment list, looking for a hole which satisfies the
+ requirements. At each point i we ask the question "can we use
+ the hole in between segments[i-1] and segments[i] ?" */
+ i_any = i_fixed = -1;
+ hstart_any = hstart_fixed = 0;
+
+ hole_start = hole_end = 0;
+
+ /* Iterate over all possible holes, generating them into
+ hole_start/hole_end. Filter out invalid ones. Then see if any
+ are usable; if so set i_fixed/i_any and hstart_fixed/hstart_any.
+ */
+ for (i = 0; i <=/*yes,really*/ segments_used; i++) {
+ if (i == 0) {
+ hole_start = 0;
+ hole_end = segments[0].addr-1;
+ }
+ else {
+ vg_assert(segments_used > 0);
+ if (i == segments_used) {
+ hole_start = segments[i-1].addr + segments[i-1].len;
+ hole_end = ~(Addr)0;
+ } else {
+ hole_start = segments[i-1].addr + segments[i-1].len;
+ hole_end = segments[i].addr - 1;
+ }
+ }
+
+ vg_assert(hole_start <= hole_end || hole_start == hole_end+1);
+
+ /* ignore zero-sized holes */
+ if (hole_start == hole_end+1)
+ continue;
+
+ vg_assert(IS_PAGE_ALIGNED(hole_start));
+ vg_assert(IS_PAGE_ALIGNED(hole_end+1));
+
+ /* ignore holes which fall outside the allowable area */
+ if (!(hole_start >= base && hole_end <= limit))
+ continue;
+
+ vg_assert(hole_end > hole_start);
+ hole_len = hole_end - hole_start + 1;
+
+ if (hole_len >= len && i_any == -1) {
+ /* It will at least fit in this hole. */
+ i_any = i;
+ hstart_any = hole_start;
+ }
+
+ if (fixed && hole_start <= addr && hole_len >= len) {
+ /* We were asked for a fixed mapping, and this hole works.
+ Bag it -- and stop searching as further searching is
+ pointless. */
+ i_fixed = i;
+ hstart_fixed = hole_start;
+ break;
+ }
+ }
+
+ /* Summarise the final decision into i_final/hstart_final. */
+ i_final = -1;
+ hstart_final = 0;
+
+ if (fixed) {
+ i_final = i_fixed;
+ hstart_final = hstart_fixed;
+ } else {
+ i_final = i_any;
+ hstart_final = hstart_any;
+ }
+
+
+ if (i_final != -1)
+ ret = hstart_final + VKI_PAGE_SIZE; /* skip leading redzone */
+ else
+ ret = 0; /* not found */
+
+ if (debug)
+ VG_(printf)("find_map_space(%p, %d, %d) -> %p\n",
+ addr, len, for_client, ret);
+
+ return ret;
+
+ vg_assert(0);
+vg_assert(0);
+///////////
if (debug)
VG_(printf)("find_map_space: ret starts as %p-%p client=%d\n",
ret, ret+len, for_client);
@@ -564,6 +907,7 @@
Addr addr = VG_(client_base);
Segment *s = VG_(SkipNode_First)(&sk_segments);
Addr ret;
+vg_assert(0);
while (s && addr <= VG_(valgrind_last)) {
if (addr < s->addr) {
@@ -592,6 +936,7 @@
Addr addr = VG_(client_base);
Segment *s = VG_(SkipNode_First)(&sk_segments);
Int ret;
+vg_assert(0);
while (s && addr <= VG_(valgrind_last)) {
if (addr < s->addr) {
@@ -609,18 +954,52 @@
return;
}
+/* Find the segment holding 'a', or NULL if none. */
Segment *VG_(find_segment)(Addr a)
{
+ Int r = find_segment(a);
+ if (0) show_segments("find_segment");
+ if (r == -1) return NULL;
+ return &segments[r];
+vg_assert(0);
return VG_(SkipList_Find)(&sk_segments, &a);
}
+/* Assumes that 'a' is not in any segment. Finds the lowest-addressed
+ segment above 'a', or NULL if none. Passing 'a' which is in fact in
+ a segment is a checked error.
+*/
+Segment *VG_(find_segment_above_unmapped)(Addr a)
+{
+ Int r = find_segment_above_unmapped(a);
+ if (0) show_segments("find_segment_above_unmapped");
+ if (r == -1) return NULL;
+ return &segments[r];
+}
+
+/* Assumes that 'a' is in some segment. Finds the next segment along,
+ or NULL if none. Passing 'a' which is in fact not in a segment is
+ a checked error.
+*/
+Segment *VG_(find_segment_above_mapped)(Addr a)
+{
+ Int r = find_segment_above_mapped(a);
+ if (0) show_segments("find_segment_above_mapped");
+ if (r == -1) return NULL;
+ return &segments[r];
+}
+
+
+
Segment *VG_(first_segment)(void)
{
+vg_assert(0);
return VG_(SkipNode_First)(&sk_segments);
}
Segment *VG_(next_segment)(Segment *s)
{
+vg_assert(0);
return VG_(SkipNode_Next)(&sk_segments, s);
}
@@ -740,6 +1119,7 @@
Addr VG_(client_alloc)(Addr addr, SizeT len, UInt prot, UInt sf_flags)
{
len = PGROUNDUP(len);
+vg_assert(0);
tl_assert(!(sf_flags & SF_FIXED));
tl_assert(0 == addr);
@@ -757,6 +1137,7 @@
{
Segment *s = VG_(find_segment)(addr);
+vg_assert(0);
if (s == NULL || s->addr != addr || !(s->flags & SF_CORE)) {
VG_(message)(Vg_DebugMsg, "VG_(client_free)(%p) - no CORE memory found there", addr);
return;
@@ -776,36 +1157,43 @@
Bool VG_(is_shadow_addr)(Addr a)
{
+vg_assert(0);
return a >= VG_(shadow_base) && a < VG_(shadow_end);
}
Bool VG_(is_valgrind_addr)(Addr a)
{
+vg_assert(0);
return a >= VG_(valgrind_base) && a <= VG_(valgrind_last);
}
Addr VG_(get_client_base)(void)
{
+vg_assert(0);
return VG_(client_base);
}
Addr VG_(get_client_end)(void)
{
+vg_assert(0);
return VG_(client_end);
}
Addr VG_(get_client_size)(void)
{
+vg_assert(0);
return VG_(client_end)-VG_(client_base);
}
Addr VG_(get_shadow_base)(void)
{
+vg_assert(0);
return VG_(shadow_base);
}
Addr VG_(get_shadow_end)(void)
{
+vg_assert(0);
return VG_(shadow_end);
}
@@ -820,6 +1208,7 @@
void VG_(init_shadow_range)(Addr p, UInt sz, Bool call_init)
{
+vg_assert(0);
if (0)
VG_(printf)("init_shadow_range(%p, %d)\n", p, sz);
@@ -845,6 +1234,7 @@
{
static Addr shadow_alloc = 0;
void *ret;
+vg_assert(0);
vg_assert(VG_(needs).shadow_memory);
vg_assert(!VG_(defined_init_shadow_page)());