From 9e8519b7a2c765b427f85f0aaa456256785eceb7 Mon Sep 17 00:00:00 2001 From: Ben Noordhuis Date: Thu, 5 Apr 2018 23:26:06 +0200 Subject: fix use-after-free in BufMap.set() closes #879 --- std/buf_map.zig | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) (limited to 'std/buf_map.zig') diff --git a/std/buf_map.zig b/std/buf_map.zig index a58df4b2db..7e2ea99f1a 100644 --- a/std/buf_map.zig +++ b/std/buf_map.zig @@ -31,8 +31,8 @@ pub const BufMap = struct { if (self.hash_map.get(key)) |entry| { const value_copy = try self.copy(value); errdefer self.free(value_copy); - _ = try self.hash_map.put(key, value_copy); - self.free(entry.value); + const old_value = ??(try self.hash_map.put(key, value_copy)); + self.free(old_value); } else { const key_copy = try self.copy(key); errdefer self.free(key_copy); @@ -71,3 +71,29 @@ pub const BufMap = struct { return result; } }; + +const assert = @import("debug/index.zig").assert; +const heap = @import("heap.zig"); + +test "BufMap" { + var direct_allocator = heap.DirectAllocator.init(); + defer direct_allocator.deinit(); + + var bufmap = BufMap.init(&direct_allocator.allocator); + defer bufmap.deinit(); + + try bufmap.set("x", "1"); + assert(mem.eql(u8, ??bufmap.get("x"), "1")); + assert(1 == bufmap.count()); + + try bufmap.set("x", "2"); + assert(mem.eql(u8, ??bufmap.get("x"), "2")); + assert(1 == bufmap.count()); + + try bufmap.set("x", "3"); + assert(mem.eql(u8, ??bufmap.get("x"), "3")); + assert(1 == bufmap.count()); + + bufmap.delete("x"); + assert(0 == bufmap.count()); +} -- cgit v1.2.3 From 58c6424d4fe64f88e25714d20d5755d31a7775c1 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 11 Apr 2018 00:32:42 -0400 Subject: simplify and fix BufMap logic --- std/buf_map.zig | 33 ++++++++++++--------------------- std/hash_map.zig | 6 +++++- 2 files changed, 17 insertions(+), 22 deletions(-) (limited to 'std/buf_map.zig') diff --git a/std/buf_map.zig b/std/buf_map.zig index 7e2ea99f1a..3e12d9a7d9 100644 --- a/std/buf_map.zig +++ b/std/buf_map.zig @@ -1,6 +1,8 @@ -const HashMap = @import("hash_map.zig").HashMap; -const mem = @import("mem.zig"); +const std = @import("index.zig"); +const HashMap = std.HashMap; +const mem = std.mem; const Allocator = mem.Allocator; +const assert = std.debug.assert; /// BufMap copies keys and values before they go into the map, and /// frees them when they get removed. @@ -28,18 +30,12 @@ pub const BufMap = struct { } pub fn set(self: &BufMap, key: []const u8, value: []const u8) !void { - if (self.hash_map.get(key)) |entry| { - const value_copy = try self.copy(value); - errdefer self.free(value_copy); - const old_value = ??(try self.hash_map.put(key, value_copy)); - self.free(old_value); - } else { - const key_copy = try self.copy(key); - errdefer self.free(key_copy); - const value_copy = try self.copy(value); - errdefer self.free(value_copy); - _ = try self.hash_map.put(key_copy, value_copy); - } + self.delete(key); + const key_copy = try self.copy(key); + errdefer self.free(key_copy); + const value_copy = try self.copy(value); + errdefer self.free(value_copy); + _ = try self.hash_map.put(key_copy, value_copy); } pub fn get(self: &BufMap, key: []const u8) ?[]const u8 { @@ -66,17 +62,12 @@ pub const BufMap = struct { } fn copy(self: &BufMap, value: []const u8) ![]const u8 { - const result = try self.hash_map.allocator.alloc(u8, value.len); - mem.copy(u8, result, value); - return result; + return mem.dupe(self.hash_map.allocator, u8, value); } }; -const assert = @import("debug/index.zig").assert; -const heap = @import("heap.zig"); - test "BufMap" { - var direct_allocator = heap.DirectAllocator.init(); + var direct_allocator = std.heap.DirectAllocator.init(); defer direct_allocator.deinit(); var bufmap = BufMap.init(&direct_allocator.allocator); diff --git a/std/hash_map.zig b/std/hash_map.zig index becced64ff..29dd233753 100644 --- a/std/hash_map.zig +++ b/std/hash_map.zig @@ -114,6 +114,7 @@ pub fn HashMap(comptime K: type, comptime V: type, } pub fn remove(hm: &Self, key: K) ?&Entry { + if (hm.entries.len == 0) return null; hm.incrementModificationCount(); const start_index = hm.keyToIndex(key); {var roll_over: usize = 0; while (roll_over <= hm.max_distance_from_start_index) : (roll_over += 1) { @@ -236,7 +237,10 @@ pub fn HashMap(comptime K: type, comptime V: type, } test "basic hash map usage" { - var map = HashMap(i32, i32, hash_i32, eql_i32).init(debug.global_allocator); + var direct_allocator = std.heap.DirectAllocator.init(); + defer direct_allocator.deinit(); + + var map = HashMap(i32, i32, hash_i32, eql_i32).init(&direct_allocator.allocator); defer map.deinit(); assert((map.put(1, 11) catch unreachable) == null); -- cgit v1.2.3 From e907c5cab971428607f85b6df4b4f7dc555775d3 Mon Sep 17 00:00:00 2001 From: Braedon Date: Thu, 3 May 2018 23:54:33 +1000 Subject: Unified API --- std/array_list.zig | 56 +++++++++++++++++++++++++++++++++++++++++++++++++++++- std/buf_map.zig | 4 ++-- std/buf_set.zig | 3 +-- std/hash_map.zig | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 110 insertions(+), 6 deletions(-) (limited to 'std/buf_map.zig') diff --git a/std/array_list.zig b/std/array_list.zig index 2a44b66518..bd7e8ea7ed 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -44,6 +44,10 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type{ return l.toSliceConst()[n]; } + pub fn count(self: &const Self) usize { + return self.len; + } + /// ArrayList takes ownership of the passed in slice. The slice must have been /// allocated with `allocator`. /// Deinitialize with `deinit` or use `toOwnedSlice`. @@ -128,6 +132,27 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type{ return null; return self.pop(); } + + pub const Iterator = struct { + list: &const Self, + // how many items have we returned + count: usize, + + pub fn next(it: &Iterator) ?T { + if (it.count >= it.list.len) return null; + const val = it.list.at(it.count); + it.count += 1; + return val; + } + + pub fn reset(it: &Iterator) void { + it.count = 0; + } + }; + + pub fn iterator(self: &Self) Iterator { + return Iterator { .list = self, .count = 0 }; + } }; } @@ -157,6 +182,35 @@ test "basic ArrayList test" { assert(list.len == 9); } +test "iterator ArrayList test" { + var list = ArrayList(i32).init(debug.global_allocator); + defer list.deinit(); + + try list.append(1); + try list.append(2); + try list.append(3); + + var count : i32 = 0; + var it = list.iterator(); + while (it.next()) |next| { + assert(next == count + 1); + count += 1; + } + + assert(count == 3); + assert(it.next() == null); + it.reset(); + count = 0; + while (it.next()) |next| { + assert(next == count + 1); + count += 1; + if (count == 2) break; + } + + it.reset(); + assert(?? it.next() == 1); +} + test "insert ArrayList test" { var list = ArrayList(i32).init(debug.global_allocator); defer list.deinit(); @@ -174,4 +228,4 @@ test "insert ArrayList test" { const items = []const i32 { 1 }; try list.insertSlice(0, items[0..0]); assert(list.items[0] == 5); -} +} \ No newline at end of file diff --git a/std/buf_map.zig b/std/buf_map.zig index 3e12d9a7d9..3b88b7a753 100644 --- a/std/buf_map.zig +++ b/std/buf_map.zig @@ -50,7 +50,7 @@ pub const BufMap = struct { } pub fn count(self: &const BufMap) usize { - return self.hash_map.size; + return self.hash_map.count(); } pub fn iterator(self: &const BufMap) BufMapHashMap.Iterator { @@ -87,4 +87,4 @@ test "BufMap" { bufmap.delete("x"); assert(0 == bufmap.count()); -} +} \ No newline at end of file diff --git a/std/buf_set.zig b/std/buf_set.zig index 618b985c41..4b89d495da 100644 --- a/std/buf_set.zig +++ b/std/buf_set.zig @@ -38,7 +38,7 @@ pub const BufSet = struct { } pub fn count(self: &const BufSet) usize { - return self.hash_map.size; + return self.hash_map.count(); } pub fn iterator(self: &const BufSet) BufSetHashMap.Iterator { @@ -59,4 +59,3 @@ pub const BufSet = struct { return result; } }; - diff --git a/std/hash_map.zig b/std/hash_map.zig index 29dd233753..99b0c58f40 100644 --- a/std/hash_map.zig +++ b/std/hash_map.zig @@ -54,6 +54,14 @@ pub fn HashMap(comptime K: type, comptime V: type, } unreachable; // no next item } + + // Reset the iterator to the initial index + pub fn reset(it: &Iterator) void { + it.count = 0; + it.index = 0; + // Resetting the modification count too + it.initial_modification_count = it.hm.modification_count; + } }; pub fn init(allocator: &Allocator) Self { @@ -79,6 +87,10 @@ pub fn HashMap(comptime K: type, comptime V: type, hm.incrementModificationCount(); } + pub fn count(hm: &const Self) usize { + return hm.size; + } + /// Returns the value that was already there. pub fn put(hm: &Self, key: K, value: &const V) !?V { if (hm.entries.len == 0) { @@ -258,10 +270,49 @@ test "basic hash map usage" { assert(map.get(2) == null); } +test "iterator hash map" { + var direct_allocator = std.heap.DirectAllocator.init(); + defer direct_allocator.deinit(); + + var reset_map = HashMap(i32, i32, hash_i32, eql_i32).init(&direct_allocator.allocator); + defer reset_map.deinit(); + + assert((reset_map.put(1, 11) catch unreachable) == null); + assert((reset_map.put(2, 22) catch unreachable) == null); + assert((reset_map.put(3, 33) catch unreachable) == null); + + var keys = []i32 { 1, 2, 3 }; + var values = []i32 { 11, 22, 33 }; + + var it = reset_map.iterator(); + var count : usize = 0; + while (it.next()) |next| { + assert(next.key == keys[count]); + assert(next.value == values[count]); + count += 1; + } + + assert(count == 3); + assert(it.next() == null); + it.reset(); + count = 0; + while (it.next()) |next| { + assert(next.key == keys[count]); + assert(next.value == values[count]); + count += 1; + if (count == 2) break; + } + + it.reset(); + var entry = ?? it.next(); + assert(entry.key == keys[0]); + assert(entry.value == values[0]); +} + fn hash_i32(x: i32) u32 { return @bitCast(u32, x); } fn eql_i32(a: i32, b: i32) bool { return a == b; -} +} \ No newline at end of file -- cgit v1.2.3 From 87c0060e813be6ee9b449058b4288d148706f8a4 Mon Sep 17 00:00:00 2001 From: Jimmi Holst Christensen Date: Fri, 4 May 2018 23:48:14 +0200 Subject: Made container methods that can be const, const --- std/array_list.zig | 16 ++++++++++++---- std/buf_map.zig | 12 ++++++------ std/buf_set.zig | 27 +++++++++++++++++++++++---- std/buffer.zig | 4 ++-- std/hash_map.zig | 15 ++++++++------- 5 files changed, 51 insertions(+), 23 deletions(-) (limited to 'std/buf_map.zig') diff --git a/std/array_list.zig b/std/array_list.zig index bd7e8ea7ed..f1881cd7f3 100644 --- a/std/array_list.zig +++ b/std/array_list.zig @@ -28,11 +28,11 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type{ }; } - pub fn deinit(l: &Self) void { + pub fn deinit(l: &const Self) void { l.allocator.free(l.items); } - pub fn toSlice(l: &Self) []align(A) T { + pub fn toSlice(l: &const Self) []align(A) T { return l.items[0..l.len]; } @@ -150,7 +150,7 @@ pub fn AlignedArrayList(comptime T: type, comptime A: u29) type{ } }; - pub fn iterator(self: &Self) Iterator { + pub fn iterator(self: &const Self) Iterator { return Iterator { .list = self, .count = 0 }; } }; @@ -168,6 +168,14 @@ test "basic ArrayList test" { assert(list.items[i] == i32(i + 1)); }} + for (list.toSlice()) |v, i| { + assert(v == i32(i + 1)); + } + + for (list.toSliceConst()) |v, i| { + assert(v == i32(i + 1)); + } + assert(list.pop() == 10); assert(list.len == 9); @@ -228,4 +236,4 @@ test "insert ArrayList test" { const items = []const i32 { 1 }; try list.insertSlice(0, items[0..0]); assert(list.items[0] == 5); -} \ No newline at end of file +} diff --git a/std/buf_map.zig b/std/buf_map.zig index 3b88b7a753..57c5830bbe 100644 --- a/std/buf_map.zig +++ b/std/buf_map.zig @@ -18,10 +18,10 @@ pub const BufMap = struct { return self; } - pub fn deinit(self: &BufMap) void { + pub fn deinit(self: &const BufMap) void { var it = self.hash_map.iterator(); while (true) { - const entry = it.next() ?? break; + const entry = it.next() ?? break; self.free(entry.key); self.free(entry.value); } @@ -38,7 +38,7 @@ pub const BufMap = struct { _ = try self.hash_map.put(key_copy, value_copy); } - pub fn get(self: &BufMap, key: []const u8) ?[]const u8 { + pub fn get(self: &const BufMap, key: []const u8) ?[]const u8 { const entry = self.hash_map.get(key) ?? return null; return entry.value; } @@ -57,11 +57,11 @@ pub const BufMap = struct { return self.hash_map.iterator(); } - fn free(self: &BufMap, value: []const u8) void { + fn free(self: &const BufMap, value: []const u8) void { self.hash_map.allocator.free(value); } - fn copy(self: &BufMap, value: []const u8) ![]const u8 { + fn copy(self: &const BufMap, value: []const u8) ![]const u8 { return mem.dupe(self.hash_map.allocator, u8, value); } }; @@ -87,4 +87,4 @@ test "BufMap" { bufmap.delete("x"); assert(0 == bufmap.count()); -} \ No newline at end of file +} diff --git a/std/buf_set.zig b/std/buf_set.zig index 4b89d495da..1badb5bf18 100644 --- a/std/buf_set.zig +++ b/std/buf_set.zig @@ -1,6 +1,8 @@ +const std = @import("index.zig"); const HashMap = @import("hash_map.zig").HashMap; const mem = @import("mem.zig"); const Allocator = mem.Allocator; +const assert = std.debug.assert; pub const BufSet = struct { hash_map: BufSetHashMap, @@ -14,10 +16,10 @@ pub const BufSet = struct { return self; } - pub fn deinit(self: &BufSet) void { + pub fn deinit(self: &const BufSet) void { var it = self.hash_map.iterator(); while (true) { - const entry = it.next() ?? break; + const entry = it.next() ?? break; self.free(entry.key); } @@ -49,13 +51,30 @@ pub const BufSet = struct { return self.hash_map.allocator; } - fn free(self: &BufSet, value: []const u8) void { + fn free(self: &const BufSet, value: []const u8) void { self.hash_map.allocator.free(value); } - fn copy(self: &BufSet, value: []const u8) ![]const u8 { + fn copy(self: &const BufSet, value: []const u8) ![]const u8 { const result = try self.hash_map.allocator.alloc(u8, value.len); mem.copy(u8, result, value); return result; } }; + +test "BufSet" { + var direct_allocator = std.heap.DirectAllocator.init(); + defer direct_allocator.deinit(); + + var bufset = BufSet.init(&direct_allocator.allocator); + defer bufset.deinit(); + + try bufset.put("x"); + assert(bufset.count() == 1); + bufset.delete("x"); + assert(bufset.count() == 0); + + try bufset.put("x"); + try bufset.put("y"); + try bufset.put("z"); +} diff --git a/std/buffer.zig b/std/buffer.zig index e0892d5933..041d891dec 100644 --- a/std/buffer.zig +++ b/std/buffer.zig @@ -66,7 +66,7 @@ pub const Buffer = struct { self.list.deinit(); } - pub fn toSlice(self: &Buffer) []u8 { + pub fn toSlice(self: &const Buffer) []u8 { return self.list.toSlice()[0..self.len()]; } @@ -166,5 +166,5 @@ test "simple Buffer" { assert(buf.endsWith("orld")); try buf2.resize(4); - assert(buf.startsWith(buf2.toSliceConst())); + assert(buf.startsWith(buf2.toSlice())); } diff --git a/std/hash_map.zig b/std/hash_map.zig index 99b0c58f40..2a178d9d44 100644 --- a/std/hash_map.zig +++ b/std/hash_map.zig @@ -74,7 +74,7 @@ pub fn HashMap(comptime K: type, comptime V: type, }; } - pub fn deinit(hm: &Self) void { + pub fn deinit(hm: &const Self) void { hm.allocator.free(hm.entries); } @@ -114,14 +114,14 @@ pub fn HashMap(comptime K: type, comptime V: type, return hm.internalPut(key, value); } - pub fn get(hm: &Self, key: K) ?&Entry { + pub fn get(hm: &const Self, key: K) ?&Entry { if (hm.entries.len == 0) { return null; } return hm.internalGet(key); } - pub fn contains(hm: &Self, key: K) bool { + pub fn contains(hm: &const Self, key: K) bool { return hm.get(key) != null; } @@ -230,7 +230,7 @@ pub fn HashMap(comptime K: type, comptime V: type, unreachable; // put into a full map } - fn internalGet(hm: &Self, key: K) ?&Entry { + fn internalGet(hm: &const Self, key: K) ?&Entry { const start_index = hm.keyToIndex(key); {var roll_over: usize = 0; while (roll_over <= hm.max_distance_from_start_index) : (roll_over += 1) { const index = (start_index + roll_over) % hm.entries.len; @@ -242,7 +242,7 @@ pub fn HashMap(comptime K: type, comptime V: type, return null; } - fn keyToIndex(hm: &Self, key: K) usize { + fn keyToIndex(hm: &const Self, key: K) usize { return usize(hash(key)) % hm.entries.len; } }; @@ -264,6 +264,7 @@ test "basic hash map usage" { assert(??(map.put(5, 66) catch unreachable) == 55); assert(??(map.put(5, 55) catch unreachable) == 66); + assert(map.contains(2)); assert((??map.get(2)).value == 22); _ = map.remove(2); assert(map.remove(2) == null); @@ -273,7 +274,7 @@ test "basic hash map usage" { test "iterator hash map" { var direct_allocator = std.heap.DirectAllocator.init(); defer direct_allocator.deinit(); - + var reset_map = HashMap(i32, i32, hash_i32, eql_i32).init(&direct_allocator.allocator); defer reset_map.deinit(); @@ -315,4 +316,4 @@ fn hash_i32(x: i32) u32 { fn eql_i32(a: i32, b: i32) bool { return a == b; -} \ No newline at end of file +} -- cgit v1.2.3