commit 0e49a0ff1fbb7c01cbf74a3fc91e8026d962c51e
Author: Chris Bracken <chris@bracken.jp>
Date: Thu, 18 Oct 2018 21:24:00 -0700
Initial version
Diffstat:
10 files changed, 317 insertions(+), 0 deletions(-)
diff --git a/.clang-format b/.clang-format
@@ -0,0 +1,12 @@
+# Defines the Chromium style for automatic reformatting.
+# http://clang.llvm.org/docs/ClangFormatStyleOptions.html
+BasedOnStyle: Chromium
+# This defaults to 'Auto'. Explicitly set it for a while, so that
+# 'vector<vector<int> >' in existing files gets formatted to
+# 'vector<vector<int>>'. ('Auto' means that clang-format will only use
+# 'int>>' if the file already contains at least one such instance.)
+Standard: Cpp11
+SortIncludes: true
+---
+Language: ObjC
+ColumnLimit: 100
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,13 @@
+# Output directories
+bin/
+lib/
+
+# CMake artifcats
+*.cmake
+CMakeCache.txt
+CMakeFiles/
+
+# Ninja artifacts
+*.ninja
+.ninja_deps
+.ninja_log
diff --git a/.gitmodules b/.gitmodules
@@ -0,0 +1,3 @@
+[submodule "third_party/googletest"]
+ path = third_party/googletest
+ url = git@github.com:google/googletest.git
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -0,0 +1,12 @@
+cmake_minimum_required(VERSION 3.0)
+
+project(foobar
+ VERSION 0.0.1
+)
+
+set(CMAKE_ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)
+set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/lib)
+set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/bin)
+
+add_subdirectory(src)
+add_subdirectory(third_party)
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,27 @@
+Copyright 2018 Chris Bracken. All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of Google Inc. nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/README.md b/README.md
@@ -0,0 +1,56 @@
+# Simple allocator
+
+A simple, poorly-performing memory allocator.
+
+## Prerequisites
+
+To build, you'll need [cmake](https://cmake.org),
+[ninja](https://github.com/ninja-build/ninja), and a clang build toolchain
+installed on your system.
+
+## Obtaining the source
+
+First, clone the repo:
+
+```shell
+git clone git@gitlab.com:cbracken/simple_allocator.git
+```
+
+Next, initialise and fetch git submodules:
+
+```shell
+# Initialise local configuration file.
+git submodule init
+
+# Fetch submodules (googletest).
+git submodule update
+```
+
+## Updating git submodules
+
+To update the git submodules to a newer commit, simply run:
+
+```shell
+git submodule update --remote
+```
+
+## Building and running
+
+First, generate the ninja build files:
+
+```shell
+# For debug build:
+cmake -DCMAKE_BUILD_TYPE=Debug -GNinja
+
+# For release build:
+cmake -DCMAKE_BUILD_TYPE=Release -GNinja
+```
+
+### Executable binary
+
+To build and run the binary:
+
+```shell
+ninja
+./bin/main
+```
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -0,0 +1,18 @@
+add_definitions(-std=c++17)
+
+set(CXX_FLAGS
+ "-Weverything"
+ "-Wno-c++98-compat"
+ "-Wno-deprecated-declarations"
+ "-Wno-padded"
+)
+
+set(CXX_TEST_FLAGS
+ ${CXX_FLAGS}
+ "-Wno-global-constructors"
+)
+
+add_executable(main
+ main.cc
+)
+target_compile_options(main PRIVATE ${CXX_FLAGS})
diff --git a/src/main.cc b/src/main.cc
@@ -0,0 +1,174 @@
+#include <iostream>
+#include <unistd.h>
+
+struct header_t {
+ size_t size;
+ struct header_t *next;
+ unsigned char is_free;
+};
+
+struct header_t *get_free_block(size_t size);
+void *malloc(size_t size);
+void print_brk();
+void print_header(struct header_t *header);
+void print_block(void *p);
+void print_alloc_list();
+
+namespace {
+struct header_t *head, *tail;
+pthread_mutex_t global_malloc_lock;
+}
+
+////////////////////////////////////////////////////////////////////////
+// Implementation.
+
+/**
+ * Return the first free block of at least the specified size, or nullptr if no
+ * such block exists.
+ */
+struct header_t *get_free_block(size_t size) {
+ struct header_t *curr = head;
+ while (curr) {
+ if (curr->is_free && curr->size >= size)
+ return curr;
+ curr = curr->next;
+ }
+ return nullptr;
+}
+
+/**
+ * Allocate a block of memory of a specific size on the heap.
+ */
+void *malloc(size_t size) {
+ size_t total_size;
+ void *block;
+ struct header_t *header;
+
+ if (!size)
+ return nullptr;
+
+ // Check for free previously-allocated block of the right size.
+ pthread_mutex_lock(&global_malloc_lock);
+ header = get_free_block(size);
+ if (header) {
+ header->is_free = 0;
+ pthread_mutex_unlock(&global_malloc_lock);
+ return static_cast<void*>(header + 1);
+ }
+
+ // If none, allocate a new block.
+ total_size = sizeof(struct header_t) + size;
+ block = sbrk(static_cast<int>(total_size));
+ if (block == reinterpret_cast<void*>(-1)) {
+ pthread_mutex_unlock(&global_malloc_lock);
+ return nullptr;
+ }
+
+ header = static_cast<struct header_t*>(block);
+ header->size = size;
+ header->is_free = 0;
+ header->next = nullptr;
+ if (!head)
+ head = header;
+ if (tail)
+ tail->next = header;
+ tail = header;
+ pthread_mutex_unlock(&global_malloc_lock);
+ return static_cast<void*>(header + 1);
+}
+
+/**
+ * Frees the specified block.
+ */
+void free(void *block) {
+ if (!block)
+ return;
+
+ pthread_mutex_lock(&global_malloc_lock);
+
+ // Get block header.
+ struct header_t *header = static_cast<struct header_t*>(block) - 1;
+
+ // Check if we're the last allocated block before brk.
+ void *program_break = sbrk(0);
+
+ if (static_cast<char*>(block) + header->size == program_break) {
+ if (head == tail) {
+ head = tail = nullptr;
+ } else {
+ for (struct header_t *p = head; p != nullptr; p = p->next) {
+ if (p->next == tail) {
+ p->next = nullptr;
+ tail = p;
+ }
+ }
+ }
+ size_t total_size = sizeof(struct header_t) + header->size;
+ void *result = sbrk(-static_cast<int>(total_size));
+ std::cout << "Result: " << result << std::endl;
+ pthread_mutex_unlock(&global_malloc_lock);
+ return;
+ }
+
+ header->is_free = 1;
+ pthread_mutex_unlock(&global_malloc_lock);
+}
+
+/**
+ * Compute and report brk.
+ */
+void print_brk() {
+ void *p = sbrk(0);
+ if (p == reinterpret_cast<void*>(-1))
+ std::cerr << "sbrk() failed" << std::endl;
+ std::cout << "brk: " << p << std::endl;
+}
+
+void print_header(struct header_t *header) {
+ if (!header)
+ return;
+ std::cout << "hdr: " << header << std::endl;
+ std::cout << "size: " << header->size << std::endl;
+ std::cout << "free: " << static_cast<bool>(header->is_free) << std::endl;
+}
+
+/**
+ * Print the header for a block.
+ */
+void print_block(void *block) {
+ std::cout << "addr: " << block << std::endl;
+ if (!block)
+ return;
+ struct header_t *h = static_cast<struct header_t*>(block) - 1;
+ print_header(h);
+}
+
+/**
+ * Print the alloc list.
+ */
+void print_alloc_list() {
+ std::cout << "== head" << std::endl;
+ print_header(head);
+ std::cout << "== tail" << std::endl;
+ print_header(tail);
+}
+
+int main(int argc, char** argv) {
+ for (auto i = 0; i < argc; ++i)
+ std::cout << "argv[" << i << "]: " << argv[i] << std::endl;
+
+ print_brk();
+ print_alloc_list();
+ std::cout << std::endl;
+
+ void *p = malloc(20);
+ std::cout << "== malloc'ed block" << std::endl;
+ print_block(p);
+ print_brk();
+ print_alloc_list();
+
+ free(p);
+ std::cout << "== free'ed block" << std::endl;
+ print_brk();
+ print_alloc_list();
+}
diff --git a/third_party/CMakeLists.txt b/third_party/CMakeLists.txt
@@ -0,0 +1 @@
+add_subdirectory(googletest)
diff --git a/third_party/googletest b/third_party/googletest
@@ -0,0 +1 @@
+Subproject commit 723f26663f1585e5ac633dbdf7a5cfb669ff9ef5
