<commit_before>/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef TNT_UTILS_ALLOCATOR_H
#define TNT_UTILS_ALLOCATOR_H


#include <assert.h>
#include <stddef.h>
#include <stdlib.h>

#include <atomic>
#include <mutex>

#include <utils/compiler.h>
#include <utils/memalign.h>

namespace utils {

namespace pointermath {

template <typename P, typename T>
static inline P* add(P* a, T b) noexcept {
    return (P*)(uintptr_t(a) + uintptr_t(b));
}

template <typename P>
static inline P* align(P* p, size_t alignment) noexcept {
    // alignment must be a power-of-two
    assert(alignment && !(alignment & alignment-1));
    return (P*)((uintptr_t(p) + alignment - 1) & ~(alignment - 1));
}

template <typename P>
static inline P* align(P* p, size_t alignment, size_t offset) noexcept {
    P* const r = align(add(p, offset), alignment);
    assert(pointermath::add(r, -offset) >= p);
    return r;
}

}

/* ------------------------------------------------------------------------------------------------
 * LinearAllocator
 *
 * + Allocates blocks linearly
 * + Cannot free individual blocks
 * + Can free top of memory back up to a specified point
 * + Doesn't call destructors
 * ------------------------------------------------------------------------------------------------
 */

class LinearAllocator {
public:
    // use memory area provided
    LinearAllocator(void* begin, void* end) noexcept;

    template <typename AREA>
    explicit LinearAllocator(const AREA& area) : LinearAllocator(area.begin(), area.end()) { }

    // Allocators can't be copied
    LinearAllocator(const LinearAllocator& rhs) = delete;
    LinearAllocator& operator=(const LinearAllocator& rhs) = delete;

    // Allocators can be moved
    LinearAllocator(LinearAllocator&& rhs) noexcept;
    LinearAllocator& operator=(LinearAllocator&& rhs) noexcept;

    ~LinearAllocator() noexcept = default;

    // our allocator concept
    void* alloc(size_t size, size_t alignment = alignof(std::max_align_t), size_t extra = 0) UTILS_RESTRICT {
        // branch-less allocation
        void* const p = pointermath::align(mCurrent, alignment, extra);
        void* const c = pointermath::add(p, size);
        bool success = c <= mEnd;
        mCurrent = success ? c : mCurrent;
        return success ? p : nullptr;
    }

    // API specific to this allocator

    void *getCurrent() UTILS_RESTRICT noexcept {
        return mCurrent;
    }

    // free memory back to the specified point
    void rewind(void* p) UTILS_RESTRICT noexcept {
        assert(p>=mBegin && p<mEnd);
        mCurrent = p;
    }

    // frees all allocated blocks
    void reset() UTILS_RESTRICT noexcept {
        rewind(mBegin);
    }

    size_t allocated() const UTILS_RESTRICT noexcept {
        return uintptr_t(mCurrent) - uintptr_t(mBegin);
    }

    size_t available() const UTILS_RESTRICT noexcept {
        return uintptr_t(mEnd) - uintptr_t(mCurrent);
    }

    void swap(LinearAllocator& rhs) noexcept;

    void *base() noexcept { return mBegin; }

    // LinearAllocator shouldn't have a free() method
    // it's only needed to be compatible with STLAllocator<> below
    void free(void*) UTILS_RESTRICT noexcept { }

private:
    void* mBegin = nullptr;
    void* mEnd = nullptr;
    void* mCurrent = nullptr;
};

/* ------------------------------------------------------------------------------------------------
 * HeapAllocator
 *
 * + uses malloc() for all allocations
 * + frees blocks with free()
 * ------------------------------------------------------------------------------------------------
 */
class HeapAllocator {
public:
    HeapAllocator() noexcept = default;

    template <typename AREA>
    explicit HeapAllocator(const AREA&) { }

    // our allocator concept
    void* alloc(size_t size, size_t alignment = alignof(std::max_align_t), size_t extra = 0) {
        // this allocator doesn't support 'extra'
        assert(extra == 0);
        return aligned_alloc(size, alignment);
    }

    void free(void* p) noexcept {
        aligned_free(p);
    }

    // Allocators can't be copied
    HeapAllocator(const HeapAllocator& rhs) = delete;
    HeapAllocator& operator=(const HeapAllocator& rhs) = delete;

    // Allocators can be moved
    HeapAllocator(HeapAllocator&& rhs) noexcept = default;
    HeapAllocator& operator=(HeapAllocator&& rhs) noexcept = default;

    ~HeapAllocator() noexcept = default;

    void swap(HeapAllocator& rhs) noexcept { }
};

// ------------------------------------------------------------------------------------------------

class FreeList {
public:
    FreeList() noexcept = default;
    FreeList(void* begin, void* end, size_t elementSize, size_t alignment, size_t extra) noexcept;
    FreeList(const FreeList& rhs) = delete;
    FreeList& operator=(const FreeList& rhs) = delete;
    FreeList(FreeList&& rhs) noexcept = default;
    FreeList& operator=(FreeList&& rhs) noexcept = default;

    void* pop() noexcept {
        Node* const head = mHead;
        mHead = head ? head->next : nullptr;
        // this could indicate a use after free
        assert(!mHead || mHead >= mBegin && mHead < mEnd);
        return head;
    }

    void push(void* p) noexcept {
        assert(p);
        assert(p >= mBegin && p < mEnd);
        // TODO: assert this is one of our pointer (i.e.: it's address match one of ours)
        Node* const head = static_cast<Node*>(p);
        head->next = mHead;
        mHead = head;
    }

    void *getFirst() noexcept {
        return mHead;
    }

private:
    struct Node {
        Node* next;
    };

    static Node* init(void* begin, void* end,
            size_t elementSize, size_t alignment, size_t extra) noexcept;

    Node* mHead = nullptr;

#ifndef NDEBUG
    // These are needed only for debugging...
    void* mBegin = nullptr;
    void* mEnd = nullptr;
#endif
};

class AtomicFreeList {
public:
    AtomicFreeList() noexcept = default;
    AtomicFreeList(void* begin, void* end,
            size_t elementSize, size_t alignment, size_t extra) noexcept;
    AtomicFreeList(const FreeList& rhs) = delete;
    AtomicFreeList& operator=(const FreeList& rhs) = delete;

    void* pop() noexcept {
        Node* const storage = mStorage;

        HeadPtr newHead; // NOLINT(cppcoreguidelines-pro-type-member-init)
        HeadPtr currentHead = mHead.load();
        while (currentHead.offset >= 0) {
            Node* const next = storage[currentHead.offset].next.load(std::memory_order_relaxed);
            newHead = { next ? int32_t(next - storage) : -1, currentHead.tag + 1 };
            if (mHead.compare_exchange_weak(currentHead, newHead)) {
                // This assert needs to occur after we have validated that there was no race condition
                // Otherwise, next might already contain application data, if another thread
                // raced ahead of us after we loaded mHead, but before we loaded mHead->next.
                assert(!next || next >= storage);
                break;
            }
        }<commit_msg>More documentation of the free list<commit_after>/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef TNT_UTILS_ALLOCATOR_H
#define TNT_UTILS_ALLOCATOR_H


#include <assert.h>
#include <stddef.h>
#include <stdlib.h>

#include <atomic>
#include <mutex>

#include <utils/compiler.h>
#include <utils/memalign.h>

namespace utils {

namespace pointermath {

template <typename P, typename T>
static inline P* add(P* a, T b) noexcept {
    return (P*)(uintptr_t(a) + uintptr_t(b));
}

template <typename P>
static inline P* align(P* p, size_t alignment) noexcept {
    // alignment must be a power-of-two
    assert(alignment && !(alignment & alignment-1));
    return (P*)((uintptr_t(p) + alignment - 1) & ~(alignment - 1));
}

template <typename P>
static inline P* align(P* p, size_t alignment, size_t offset) noexcept {
    P* const r = align(add(p, offset), alignment);
    assert(pointermath::add(r, -offset) >= p);
    return r;
}

}

/* ------------------------------------------------------------------------------------------------
 * LinearAllocator
 *
 * + Allocates blocks linearly
 * + Cannot free individual blocks
 * + Can free top of memory back up to a specified point
 * + Doesn't call destructors
 * ------------------------------------------------------------------------------------------------
 */

class LinearAllocator {
public:
    // use memory area provided
    LinearAllocator(void* begin, void* end) noexcept;

    template <typename AREA>
    explicit LinearAllocator(const AREA& area) : LinearAllocator(area.begin(), area.end()) { }

    // Allocators can't be copied
    LinearAllocator(const LinearAllocator& rhs) = delete;
    LinearAllocator& operator=(const LinearAllocator& rhs) = delete;

    // Allocators can be moved
    LinearAllocator(LinearAllocator&& rhs) noexcept;
    LinearAllocator& operator=(LinearAllocator&& rhs) noexcept;

    ~LinearAllocator() noexcept = default;

    // our allocator concept
    void* alloc(size_t size, size_t alignment = alignof(std::max_align_t), size_t extra = 0) UTILS_RESTRICT {
        // branch-less allocation
        void* const p = pointermath::align(mCurrent, alignment, extra);
        void* const c = pointermath::add(p, size);
        bool success = c <= mEnd;
        mCurrent = success ? c : mCurrent;
        return success ? p : nullptr;
    }

    // API specific to this allocator

    void *getCurrent() UTILS_RESTRICT noexcept {
        return mCurrent;
    }

    // free memory back to the specified point
    void rewind(void* p) UTILS_RESTRICT noexcept {
        assert(p>=mBegin && p<mEnd);
        mCurrent = p;
    }

    // frees all allocated blocks
    void reset() UTILS_RESTRICT noexcept {
        rewind(mBegin);
    }

    size_t allocated() const UTILS_RESTRICT noexcept {
        return uintptr_t(mCurrent) - uintptr_t(mBegin);
    }

    size_t available() const UTILS_RESTRICT noexcept {
        return uintptr_t(mEnd) - uintptr_t(mCurrent);
    }

    void swap(LinearAllocator& rhs) noexcept;

    void *base() noexcept { return mBegin; }

    // LinearAllocator shouldn't have a free() method
    // it's only needed to be compatible with STLAllocator<> below
    void free(void*) UTILS_RESTRICT noexcept { }

private:
    void* mBegin = nullptr;
    void* mEnd = nullptr;
    void* mCurrent = nullptr;
};

/* ------------------------------------------------------------------------------------------------
 * HeapAllocator
 *
 * + uses malloc() for all allocations
 * + frees blocks with free()
 * ------------------------------------------------------------------------------------------------
 */
class HeapAllocator {
public:
    HeapAllocator() noexcept = default;

    template <typename AREA>
    explicit HeapAllocator(const AREA&) { }

    // our allocator concept
    void* alloc(size_t size, size_t alignment = alignof(std::max_align_t), size_t extra = 0) {
        // this allocator doesn't support 'extra'
        assert(extra == 0);
        return aligned_alloc(size, alignment);
    }

    void free(void* p) noexcept {
        aligned_free(p);
    }

    // Allocators can't be copied
    HeapAllocator(const HeapAllocator& rhs) = delete;
    HeapAllocator& operator=(const HeapAllocator& rhs) = delete;

    // Allocators can be moved
    HeapAllocator(HeapAllocator&& rhs) noexcept = default;
    HeapAllocator& operator=(HeapAllocator&& rhs) noexcept = default;

    ~HeapAllocator() noexcept = default;

    void swap(HeapAllocator& rhs) noexcept { }
};

// ------------------------------------------------------------------------------------------------

class FreeList {
public:
    FreeList() noexcept = default;
    FreeList(void* begin, void* end, size_t elementSize, size_t alignment, size_t extra) noexcept;
    FreeList(const FreeList& rhs) = delete;
    FreeList& operator=(const FreeList& rhs) = delete;
    FreeList(FreeList&& rhs) noexcept = default;
    FreeList& operator=(FreeList&& rhs) noexcept = default;

    void* pop() noexcept {
        Node* const head = mHead;
        mHead = head ? head->next : nullptr;
        // this could indicate a use after free
        assert(!mHead || mHead >= mBegin && mHead < mEnd);
        return head;
    }

    void push(void* p) noexcept {
        assert(p);
        assert(p >= mBegin && p < mEnd);
        // TODO: assert this is one of our pointer (i.e.: it's address match one of ours)
        Node* const head = static_cast<Node*>(p);
        head->next = mHead;
        mHead = head;
    }

    void *getFirst() noexcept {
        return mHead;
    }

private:
    struct Node {
        Node* next;
    };

    static Node* init(void* begin, void* end,
            size_t elementSize, size_t alignment, size_t extra) noexcept;

    Node* mHead = nullptr;

#ifndef NDEBUG
    // These are needed only for debugging...
    void* mBegin = nullptr;
    void* mEnd = nullptr;
#endif
};

class AtomicFreeList {
public:
    AtomicFreeList() noexcept = default;
    AtomicFreeList(void* begin, void* end,
            size_t elementSize, size_t alignment, size_t extra) noexcept;
    AtomicFreeList(const FreeList& rhs) = delete;
    AtomicFreeList& operator=(const FreeList& rhs) = delete;

    void* pop() noexcept {
        Node* const storage = mStorage;

        HeadPtr newHead; // NOLINT(cppcoreguidelines-pro-type-member-init)
        HeadPtr currentHead = mHead.load();
        while (currentHead.offset >= 0) {
            // The value of "next" we load here might already contain application data if another
            // thread raced ahead of us. But in that case, the computed "newHead" will be discarded
            // since compare_exchange_weak fails. Then this thread will loop with the updated
            // value of currentHead, and try again.
            Node* const next = storage[currentHead.offset].next.load(std::memory_order_relaxed);
            newHead = { next ? int32_t(next - storage) : -1, currentHead.tag + 1 };
            // In the rare case that the other thread that raced ahead of us already returned the 
            // same mHead we just loaded, but it now has a different "next" value, the tag field will not 
            // match, and compare_exchange_weak will fail and prevent that particular race condition.
            if (mHead.compare_exchange_weak(currentHead, newHead)) {
                // This assert needs to occur after we have validated that there was no race condition
                // Otherwise, next might already contain application data, if another thread
                // raced ahead of us after we loaded mHead, but before we loaded mHead->next.
                assert(!next || next >= storage);
                break;
            }
        }
{'fraction_non_alphanumeric': 0.15702947845804988, 'fraction_numerical': 0.0023935500125976316, 'mean_word_length': 2.304954204829309, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4111444', 'n_tokens_mistral': 4587, 'n_tokens_neox': 4398, 'n_words': 1468}