You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2018/08/03 17:51:44 UTC
[trafficserver] branch master updated: ts/Extendible and AcidPtr
class
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 85404be ts/Extendible and AcidPtr class
85404be is described below
commit 85404becf0837bb628ebc0f97a57359cdaabb9a7
Author: Aaron Canary <ac...@oath.com>
AuthorDate: Fri Aug 3 11:08:54 2018 -0500
ts/Extendible and AcidPtr class
new classes to provide atomic field operations for the Nexthop DB.
clean up
Adds/Completes references, minor fix-ups
rst: removed template<>
---
.../internal-libraries/AcidPtr.en.rst | 286 ++++++++++
.../internal-libraries/Extendible.en.rst | 260 +++++++++
.../internal-libraries/index.en.rst | 2 +
lib/ts/AcidPtr.cc | 43 ++
lib/ts/AcidPtr.h | 199 +++++++
lib/ts/Extendible.h | 586 +++++++++++++++++++++
lib/ts/Makefile.am | 6 +-
lib/ts/unit-tests/test_AcidPtr.cc | 96 ++++
lib/ts/unit-tests/test_Extendible.cc | 286 ++++++++++
9 files changed, 1763 insertions(+), 1 deletion(-)
diff --git a/doc/developer-guide/internal-libraries/AcidPtr.en.rst b/doc/developer-guide/internal-libraries/AcidPtr.en.rst
new file mode 100644
index 0000000..3a54e4e
--- /dev/null
+++ b/doc/developer-guide/internal-libraries/AcidPtr.en.rst
@@ -0,0 +1,286 @@
+.. Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+
+.. include:: ../../common.defs
+
+.. highlight:: cpp
+.. default-domain:: cpp
+
+.. |AcidPtr| replace:: :class:`AcidPtr`
+.. |AcidCommitPtr| replace:: :class:`AcidCommitPtr`
+
+
+.. _ACIDPTR:
+
+AcidPtr & AcidCommitPtr
+***********************
+
+Synopsis
+++++++++
+
+.. code-block:: cpp
+
+ #include "ts/AcidPtr.h"
+
+|AcidPtr| provides atomic access to a std::shared_ptr.
+|AcidCommitPtr| provides exclusive write access to data.
+
+Description
++++++++++++
+
+Provides transparent interface for "copy on write" and "commit when done" in a familiar unique_ptr style.
+
+Named after the desirable properties of a database, ACID_ acronym:
+
+* Atomic - reads and writes avoid skew, by using mutex locks.
+* Consistent - data can only be changed by a commit, and only one commit can exist at a time per data.
+* Isolated - commits of a single point of data are not concurrent. But commits of seperate data can be conncurrent.
+* Durable - shared_ptr is used to keep older versions of data in memory while references exist.
+
+.. _ACID: https://en.wikipedia.org/wiki/ACID_(computer_science)
+
+.. uml:
+ class AcidPtr<T> {
+ -std::shared_ptr<T> data
+ ----
+ +AcidPtr()
+ +AcidPtr(T*)
+ +std::shared_ptr<const T> getPtr()
+ +void commit(T*)
+ +AcidCommmitPtr<T> startCommit()
+ ----
+ ~_finishCommit(T*)
+ }
+
+ class AcidCommitPtr<T> {
+ -AcidPtr& data_ptr
+ -std::unique_lock commit_lock
+ ----
+ -AcidCommmitPtr() = delete
+ +AcidCommmitPtr(AcidPtr&)
+ +~AcidCommmitPtr()
+ +void abort()
+ }
+
+ class std::unique_ptr {
+
+ }
+
+ AcidCommitPtr--|>std::unique_ptr
+
+Performance
+-----------
+Note this code is currently implemented with mutex locks, it is expected to be fast due to the very brief duration of each lock. It would be plausible to change the implementation to use atomics or spin locks.
+
+
+|AcidCommitPtr|
+
+* On construction, duplicate values from a shared_ptr to a unique_ptr. (aka copy read to write memory)
+* On destruction, move value ptr to shared_ptr. (aka move write ptr to read ptr)
+
+The |AcidCommitPtr| executes this transparent to the writer code. It copies the data on construction, and finalizes on destruction. A MemLock is used to allow exclusive read and write access, however the access is made to as fast as possible.
+
+Use Cases
+---------
+Implemented for use |ACIDPTR| interface in :class:`Extendible`. But could be used elsewhere without modification.
+
+.. uml::
+ :align: center
+
+ title Read while Write
+
+ actor ExistingReaders
+ actor NewReaders
+ actor Writer
+ storage AcidPtr
+ card "x=foo" as Data
+ card "x=bar" as DataPrime
+
+ ExistingReaders --> Data : read only
+ AcidPtr -> Data : shared_ptr
+ NewReaders --> AcidPtr : read only
+ Writer --> DataPrime : read/write
+ Data .> DataPrime : copy
+
+When the writer is done, :func:`~AcidCommitPtr::~AcidCommitPtr()` is called and its |AcidPtr| is updated to point at the written copy, so that future read requests will use it. Existing reader will continue to use the old data.
+
+.. uml::
+ :align: center
+
+ title Write Finalize
+
+ actor ExistingReaders
+ actor NewReaders
+ storage AcidPtr
+ card "x=foo" as Data
+ card "x=bar" as DataPrime
+
+ ExistingReaders --> Data : read only
+ AcidPtr -> DataPrime : shared_ptr
+ NewReaders --> AcidPtr : read only
+
+
+.. uml::
+ :align: center
+
+ title AcidPtr Reader/Reader Contention
+ box "MemLock"
+ participant "Access" as AccessMutex
+ end box
+ participant AcidPtr
+ actor Reader_A #green
+ actor Reader_B #red
+ Reader_A -[#green]> AcidPtr: getPtr()
+ AcidPtr <[#green]- AccessMutex: lock
+ activate AccessMutex #green
+ Reader_B -> AcidPtr: getPtr()
+ AcidPtr -[#green]> Reader_A: copy const shared_ptr
+ activate Reader_A
+ note left
+ Contention limited to
+ duration of shared_ptr copy.
+ (internally defined)
+ end note
+ AcidPtr -[#green]> AccessMutex: unlock
+ deactivate AccessMutex
+ AcidPtr <- AccessMutex: lock
+ activate AccessMutex #red
+ AcidPtr -> Reader_B: copy const shared_ptr
+ activate Reader_B
+ AcidPtr -> AccessMutex: unlock
+ deactivate AccessMutex
+
+
+.. uml::
+ :align: center
+
+ Title AcidPtr Writer/Reader Contention
+ box "MemLock"
+ participant "Access" as AccessMutex
+ participant "Write" as WriteMutex
+ end box
+ participant AcidPtr
+ actor Writer #red
+ actor Reader #green
+
+ Writer -> AcidPtr: startCommit()
+ AcidPtr <- WriteMutex: lock
+ activate WriteMutex #red
+ AcidPtr -> Writer: copy to AcidCommitPtr
+ activate Writer
+ hnote over Writer #pink
+ update AcidCommitPtr
+ end hnote
+ Reader -[#green]> AcidPtr: getPtr()
+ AcidPtr <[#green]- AccessMutex: lock
+ activate AccessMutex #green
+
+ Writer -> AcidPtr: ~AcidCommitPtr()
+ deactivate Writer
+ AcidPtr -[#green]> Reader: copy const shared_ptr
+ activate Reader
+ note left
+ Contention limited to duration
+ of shared_ptr copy/reset.
+ (internally defined)
+ end note
+ AcidPtr -[#green]> AccessMutex: unlock
+ deactivate AccessMutex
+
+ AcidPtr <- AccessMutex: lock
+ activate AccessMutex #red
+ hnote over Reader #lightgreen
+ use shared copy
+ end hnote
+ AcidPtr -> AcidPtr: reset shared_ptr
+ AcidPtr -> AccessMutex: unlock
+ deactivate AccessMutex
+ AcidPtr -> WriteMutex: unlock
+ deactivate WriteMutex
+
+
+.. uml::
+ :align: center
+
+ Title AcidPtr Writer/Writer Contention
+ box "MemLock"
+ participant "Access" as AccessMutex
+ participant "Write" as WriteMutex
+ end box
+ participant AcidPtr
+ actor Writer_A #red
+ actor Writer_B #blue
+
+ Writer_A -> AcidPtr: startCommit
+ AcidPtr <- WriteMutex: lock
+ activate WriteMutex #red
+ AcidPtr -> Writer_A: copy to AcidCommitPtr
+ activate Writer_A
+ Writer_B -[#blue]> AcidPtr: startCommit
+ hnote over Writer_A #pink
+ update AcidCommitPtr
+ end hnote
+ note over Writer_A
+ Contention for duration
+ of AcidCommitPtr scope.
+ (externally defined)
+ end note
+ Writer_A -> AcidPtr: ~AcidCommitPtr()
+ deactivate Writer_A
+ AcidPtr <- AccessMutex: lock
+ activate AccessMutex #red
+ AcidPtr -> AcidPtr: reset shared_ptr
+ AcidPtr -> AccessMutex: unlock
+ deactivate AccessMutex
+ AcidPtr -> WriteMutex: unlock
+ deactivate WriteMutex
+
+ AcidPtr <[#blue]- WriteMutex: lock
+ activate WriteMutex #blue
+ AcidPtr -[#blue]> Writer_B: copy to AcidCommitPtr
+ activate Writer_B
+ hnote over Writer_B #lightblue
+ update AcidCommitPtr
+ end hnote
+ Writer_B -[#blue]> AcidPtr: ~AcidCommitPtr()
+ deactivate Writer_B
+ deactivate AccessMutex
+
+ AcidPtr <[#blue]- AccessMutex: lock
+ activate AccessMutex #blue
+ AcidPtr -[#blue]> AcidPtr: reset shared_ptr
+ AcidPtr -[#blue]> AccessMutex: unlock
+ deactivate AccessMutex
+ AcidPtr -[#blue]> WriteMutex: unlock
+ deactivate WriteMutex
+
+Reference
++++++++++
+
+
+.. class:: template<typename T> AcidPtr
+
+ .. function:: template<typename T> const std::shared_ptr<const T> getPtr() const
+
+.. class:: template<typename T> AcidCommitPtr
+
+ .. function:: template<> ~AcidCommitPtr()
+
+ .. function:: template<T> AcidCommitPtr<T> startCommit()
+
+ .. function:: template<> void abort()
+
diff --git a/doc/developer-guide/internal-libraries/Extendible.en.rst b/doc/developer-guide/internal-libraries/Extendible.en.rst
new file mode 100644
index 0000000..7fe049a
--- /dev/null
+++ b/doc/developer-guide/internal-libraries/Extendible.en.rst
@@ -0,0 +1,260 @@
+.. Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+
+.. include:: ../../common.defs
+
+.. highlight:: cpp
+.. default-domain:: cpp
+
+.. |Extendible| replace:: :class:`Extendible`
+.. |FieldId| replace:: :class:`~Extendible::FieldId`
+.. |FieldId_C| replace:: :type:`FieldId_C`
+.. |FieldSchema| replace:: :class:`~Extendible::FieldSchema`
+.. |Schema| replace:: :class:`~Extendible::Schema`
+
+.. |ATOMIC| replace:: :enumerator:`~AccessEnum::ATOMIC`
+.. |BIT| replace:: :enumerator:`~AccessEnum::BIT`
+.. |ACIDPTR| replace:: :enumerator:`~AccessEnum::ACIDPTR`
+.. |STATIC| replace:: :enumerator:`~AccessEnum::STATIC`
+.. |DIRECT| replace:: :enumerator:`~AccessEnum::DIRECT`
+.. |C_API| replace:: :enumerator:`~AccessEnum::C_API`
+
+.. _Extendible:
+
+Extendible
+**********
+
+Synopsis
+++++++++
+
+.. code-block:: cpp
+
+ #include "ts/Extendible.h"
+
+|Extendible| allows Plugins to append additional storage to Core data structures.
+
+Use Case:
+
+TSCore
+
+ Defines class ``Host`` as |Extendible|
+
+TSPlugin ``HealthStatus``
+
+ Appends field ``"down reason code"`` to ``Host``
+ Now the plugin does not need to create completely new lookup table and all implementation that comes with it.
+
+
+Description
++++++++++++
+
+A data class that inherits from Extendible, uses a CRTP (Curiously Recurring Template Pattern) so that its static |Schema| instance is unique among other |Extendible| types.
+
+.. code-block:: cpp
+
+ class ExtendibleExample : Extendible<ExtendibleExample> {
+ int real_member = 0;
+ }
+
+
+During system init, code and plugins can add fields to the |Extendible|'s schema. This will update the `Memory Layout`_ of the schema, and the memory offsets of all fields. The schema does not know the field's type, but it stores the byte size and creates lambdas of the type's constructor and destructor. And to avoid corruption, the code asserts that no instances are in use when adding fields.
+
+.. code-block:: cpp
+
+ ExtendibleExample::FieldId<ATOMIC,int> fld_my_int;
+
+ void PluginInit() {
+ fld_my_int = ExtendibleExample::schema.addField("my_plugin_int");
+ }
+
+
+When an |Extendible| derived class is instantiated, :code:`new()` will allocate a block of memory for the derived class and all added fields. There is zero memory overhead per instance, unless using :enumerator:`~AccessEnum::ACIDPTR` field access type.
+
+.. code-block:: cpp
+
+ ExtendibleExample* alloc_example() {
+ return new ExtendibleExample();
+ }
+
+Memory Layout
+-------------
+One block of memory is allocated per |Extendible|, which include all member variables and appended fields.
+Within the block, memory is arranged in the following order:
+
+#. Derived members (+padding align next field)
+#. Fields (largest to smallest)
+#. Packed Bits
+
+Strongly Typed Fields
+---------------------
+:class:`template<AccessEnum FieldAccess_e, typename T> Extendible::FieldId`
+
+|FieldId| is a templated ``T`` reference. One benefit is that all type casting is internal to the |Extendible|,
+which simplifies the code using it. Also this provides compile errors for common misuses and type mismatches.
+
+.. code-block:: cpp
+
+ // Core code
+ class Food : Extendible<Food> {}
+ class Car : Extendible<Car> {}
+
+ // Example Plugin
+ Food::FieldId<STATIC,float> fld_food_weight;
+ Food::FieldId<STATIC,time_t> fld_expr_date;
+ Car::FieldId<STATIC,float> fld_max_speed;
+ Car::FieldId<STATIC,float> fld_car_weight;
+
+ PluginInit() {
+ Food.schema.addField(fld_food_weight, "weight");
+ Food.schema.addField(fld_expr_date,"expire date");
+ Car.schema.addField(fld_max_speed,"max_speed");
+ Car.schema.addField(fld_car_weight,"weight"); // 'weight' is unique within 'Car'
+ }
+
+ PluginFunc() {
+ Food banana;
+ Car camry;
+
+ // Common user errors
+
+ float expire_date = banana.get(fld_expr_date);
+ //^^^ Compile error: cannot convert time_t to float
+ float speed = banana.get(fld_max_speed);
+ // ^^^^^^^^^^^^^ Compile error: fld_max_speed is not of type Extendible<Food>::FieldId
+ float weight = camry.get(fld_food_weight);
+ // ^^^^^^^^^^^^^^^ Compile error: fld_food_weight is not of type Extendible<Car>::FieldId
+ }
+
+Field Access Types
+------------------
+
+.. _AccessType:
+
+..
+ Currently Sphinx will link to the first overloaded version of the method /
+ function. (As of Sphinx 1.7.6)
+
+.. |GET| replace:: :func:`~Extendible::get`
+.. |READBIT| replace:: :func:`~Extendible::readBit`
+.. |WRITEBIT| replace:: :func:`~Extendible::writeBit`
+.. |WRITEACIDPTR| replace:: :func:`~Extendible::writeAcidPtr`
+.. |INIT| replace:: :func:`~Extendible::init`
+
+================ ================================= ================================================================ ================================================= ================================================
+Enums Allocates API Pros Cons
+================ ================================= ================================================================ ================================================= ================================================
+|ATOMIC| ``std::atomic<T>`` |GET| Leverages ``std::atomic`` API. No Locking. Only works on small data types.
+|BIT| 1 bit from packed bits |GET|, |READBIT|, |WRITEBIT| Memory efficient. Cannot return reference.
+|ACIDPTR| ``std::make_shared<T>`` |GET|, |WRITEACIDPTR| Avoid skew in non-atomic structures. Non-contiguous memory allocations. Uses locking.
+|STATIC| ``T`` |GET|, |INIT| Const reference. Fast. Type safe. No concurrency protection.
+|DIRECT| ``T`` |GET| Direct reference. Fast. Type safe. No concurrency protection.
+|C_API| a number of bytes |GET| Can use in C. No concurrency protection. Not type safe.
+================ ================================= ================================================================ ================================================= ================================================
+
+:code:`operator[](FieldId)` has been overridden to call :code:`get(FieldId)` for all access types.
+
+Unfortunately our data is not "one type fits all". I expect that most config values will be stored as :enumerator:`AccessEnum::STATIC`, most states values will be :enumerator:`AccessEnum::ATOMIC` or :enumerator:`AccessEnum::BIT`, while vectored results will be :enumerator:`AccessEnum::ACIDPTR`.
+
+Reference
++++++++++
+
+.. enum:: AccessEnum
+
+ .. enumerator:: ATOMIC
+
+ Represents atomic field reference (read, write or other atomic operation).
+
+ .. enumerator:: BIT
+
+ Represents compressed boolean fields.
+
+ .. enumerator:: STATIC
+
+ Represents immutable field, value is not expected to change, no internal thread safety.
+
+ .. enumerator:: ACIDPTR
+
+ Represents a pointer promising Atomicity, Consistency, Isolation, Durability
+
+ .. seealso:: :ref:`AcidPtr`
+
+ .. enumerator:: DIRECT
+
+ Represents a mutable field with no internal thread safety.
+
+ .. enumerator:: C_API
+
+ Represents C-Style pointer access.
+
+.. class:: template<typename Derived_t> Extendible
+
+ Allocates block of memory, uses |FieldId| or schema to access slices of memory.
+
+ :tparam Derived_t: The class that you want to extend at runtime.
+
+ .. class:: template<AccessEnum FieldAccess_e, typename T> FieldId
+
+ The handle used to access a field. These are templated to prevent human error, and branching logic.
+
+ :tparam FieldAccess_e: The type of access to the field.
+ :tparam T: The type of the field.
+
+ .. class:: FieldSchema
+
+ Stores attributes, constructor and destructor of a field.
+
+ .. class:: Schema
+
+ Manages fields and memory layout of an |Extendible| type.
+
+ .. function:: template<AccessEnum FieldAccess_e, typename T> bool addField(FieldId<FieldAccess_e, T> & field_id, std::string const & field_name)
+
+ Add a new field to this record type.
+
+ .. member:: static Schema schema
+
+ one schema instance per |Extendible| to define contained fields
+
+ .. function:: template<AccessEnum FieldAccess_e, typename T> std::atomic<T> & get(FieldId<AccessEnum::ATOMIC, T> const & field)
+
+ .. type:: BitFieldId = FieldId<AccessEnum::BIT, bool>
+
+ .. function:: bool const get(BitFieldId field) const
+
+ .. function:: bool const readBit(BitFieldId field) const
+
+ .. function:: void writeBit(BitFieldId field, bool const val)
+
+ .. function:: template <AccessEnum FieldAccess_e, typename T> T const & get(FieldId<AccessEnum::STATIC, T> field) const
+
+ .. function:: template <AccessEnum FieldAccess_e, typename T> T &init(FieldId<AccessEnum::STATIC, T> field)
+
+ .. function:: template <AccessEnum FieldAccess_e, typename T> std::shared_ptr<const T> get(FieldId<AccessEnum::ACIDPTR, T> field) const
+
+ .. function:: template <AccessEnum FieldAccess_e, typename T> AcidCommitPtr<T> writeAcidPtr(FieldId<AccessEnum::ACIDPTR, T> field)
+
+ .. function:: void * get(FieldId_C & field)
+
+ .. function template <AccessEnum FieldAccess_e, typename T> auto operator[](FieldId<FieldAccess_e, T> field)
+
+ :return: the result of :function:`get`
+
+
+.. type:: const void* FieldId_C
+
+ The handle used to access a field through C API. Human error not allowed by convention.
+
diff --git a/doc/developer-guide/internal-libraries/index.en.rst b/doc/developer-guide/internal-libraries/index.en.rst
index aae63c8..fd9d3af 100644
--- a/doc/developer-guide/internal-libraries/index.en.rst
+++ b/doc/developer-guide/internal-libraries/index.en.rst
@@ -34,3 +34,5 @@ development team.
buffer-writer.en
intrusive-list.en
MemArena.en
+ AcidPtr.en
+ Extendible.en
diff --git a/lib/ts/AcidPtr.cc b/lib/ts/AcidPtr.cc
new file mode 100644
index 0000000..304fb19
--- /dev/null
+++ b/lib/ts/AcidPtr.cc
@@ -0,0 +1,43 @@
+/**
+ @file AcidPtr defines global LockPools for accessing and committing
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+*/
+
+#include "AcidPtr.h"
+
+const int READLOCKCOUNT = 61; // a prime larger than number of readers
+
+AcidPtrMutex &
+AcidPtrMutexGet(void const *ptr)
+{
+ static LockPool<AcidPtrMutex> read_locks(READLOCKCOUNT);
+ static_assert(sizeof(void *) == sizeof(size_t));
+ return read_locks.getMutex(reinterpret_cast<size_t>(ptr));
+}
+
+const int WRITELOCKCOUNT = 31; // a prime larger than number of writers
+
+AcidCommitMutex &
+AcidCommitMutexGet(void const *ptr)
+{
+ static LockPool<AcidCommitMutex> write_locks(WRITELOCKCOUNT);
+ static_assert(sizeof(void *) == sizeof(size_t));
+ return write_locks.getMutex(reinterpret_cast<size_t>(ptr));
+}
diff --git a/lib/ts/AcidPtr.h b/lib/ts/AcidPtr.h
new file mode 100644
index 0000000..6656705
--- /dev/null
+++ b/lib/ts/AcidPtr.h
@@ -0,0 +1,199 @@
+/**
+ @file AcidPtr
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+
+ @section details Details
+
+////////////////////////////////////////////
+ Implements advanced locking techniques:
+ * LockPool
+ * Writer_ptr
+*/
+
+#pragma once
+#include <mutex>
+#include <vector>
+#include <memory>
+
+//////////////////////////////////////////////////////////
+// Lock Pool
+/// Intended to make datasets thread safe by assigning locks to stripes of data, kind of like a bloom filter.
+/** Allocates a fixed number of locks and retrives one with a hash.
+ */
+template <typename Mutex_t> struct LockPool {
+ /**
+ * @param numLocks - use a prime number near the number of concurrent users you expect
+ */
+ LockPool(size_t num_locks) : mutexes(num_locks) {}
+
+ Mutex_t &
+ getMutex(size_t key_hash)
+ {
+ return mutexes[key_hash % size()];
+ }
+
+ size_t
+ size() const
+ {
+ return mutexes.size();
+ }
+
+ void
+ lockAll()
+ {
+ for (Mutex_t &m : mutexes) {
+ m.lock();
+ }
+ }
+
+ void
+ unlockAll()
+ {
+ for (Mutex_t &m : mutexes) {
+ m.unlock();
+ }
+ }
+
+private:
+ std::vector<Mutex_t> mutexes;
+
+ /// use the other constructor to define how many locks you want.
+ LockPool() = delete;
+ LockPool(LockPool const &) = delete;
+};
+
+template <typename T> class AcidCommitPtr;
+template <typename T> class AcidPtr;
+
+using AcidPtrMutex = std::mutex; // TODO: use shared_mutex when available
+using AcidPtrLock = std::unique_lock<AcidPtrMutex>;
+AcidPtrMutex &AcidPtrMutexGet(void const *ptr); // used for read, and write swap
+
+using AcidCommitMutex = std::mutex;
+using AcidCommitLock = std::unique_lock<AcidCommitMutex>;
+AcidCommitMutex &AcidCommitMutexGet(void const *ptr); // used for write block
+
+///////////////////////////////////////////
+/// AcidPtr
+/** just a thread safe shared pointer.
+ *
+ */
+
+template <typename T> class AcidPtr
+{
+private:
+ std::shared_ptr<T> data_ptr;
+
+public:
+ AcidPtr(const AcidPtr &) = delete;
+ AcidPtr &operator=(const AcidPtr &) = delete;
+
+ AcidPtr() : data_ptr(new T()) {}
+ AcidPtr(T *data) : data_ptr(data) {}
+
+ const std::shared_ptr<const T>
+ getPtr() const
+ { // wait until we have exclusive pointer access.
+ auto ptr_lock = AcidPtrLock(AcidPtrMutexGet(&data_ptr));
+ // copy the pointer
+ return data_ptr;
+ //[end scope] unlock ptr_lock
+ }
+
+ void
+ commit(T *data)
+ {
+ // wait until existing commits finish, avoid race conditions
+ auto commit_lock = AcidCommitLock(AcidCommitMutexGet(&data_ptr));
+ // wait until we have exclusive pointer access.
+ auto ptr_lock = AcidPtrLock(AcidPtrMutexGet(&data_ptr));
+ // overwrite the pointer
+ data_ptr.reset(data);
+ //[end scope] unlock commit_lock & ptr_lock
+ }
+
+ AcidCommitPtr<T>
+ startCommit()
+ {
+ return AcidCommitPtr<T>(*this);
+ }
+
+ friend class AcidCommitPtr<T>;
+
+protected:
+ void
+ _finishCommit(T *data)
+ {
+ // wait until we have exclusive pointer access.
+ auto ptr_lock = AcidPtrLock(AcidPtrMutexGet(&data_ptr));
+ // overwrite the pointer
+ data_ptr.reset(data);
+ //[end scope] unlock ptr_lock
+ }
+};
+
+///////////////////////////////////////////
+/// AcidCommitPtr
+
+/// a globally exclusive pointer, for commiting changes to AcidPtr.
+/** used for COPY_SWAP functionality.
+ * 1. copy data (construct)
+ * 2. overwrite data (scope)
+ * 3. update live data pointer (destruct)
+ */
+template <typename T> class AcidCommitPtr : public std::unique_ptr<T>
+{
+private:
+ AcidCommitLock commit_lock; // block other writers from starting
+ AcidPtr<T> &data; // data location
+
+public:
+ AcidCommitPtr() = delete;
+ AcidCommitPtr(const AcidCommitPtr &) = delete;
+ AcidCommitPtr &operator=(const AcidCommitPtr<T> &) = delete;
+
+ AcidCommitPtr(AcidPtr<T> &data_ptr) : commit_lock(AcidCommitMutexGet(&data_ptr)), data(data_ptr)
+ {
+ // wait for exclusive commit access to the data
+ // copy the data to new memory
+ std::unique_ptr<T>::reset(new T(*data.getPtr()));
+ }
+ AcidCommitPtr(AcidCommitPtr &&other)
+ : std::unique_ptr<T>(std::move(other)), commit_lock(std::move(other.commit_lock)), data(other.data)
+ {
+ }
+
+ ~AcidCommitPtr()
+ {
+ if (!commit_lock) {
+ return; // previously aborted
+ }
+
+ // point the existing read ptr to the newly written data
+ data._finishCommit(std::unique_ptr<T>::release());
+ }
+
+ void
+ abort()
+ {
+ commit_lock.unlock(); // allow other writers to start
+ std::unique_ptr<T>::reset(); // delete data copy
+ }
+};
diff --git a/lib/ts/Extendible.h b/lib/ts/Extendible.h
new file mode 100644
index 0000000..f251640
--- /dev/null
+++ b/lib/ts/Extendible.h
@@ -0,0 +1,586 @@
+/** @file
+
+ Extendible
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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.
+
+ @section details Details
+
+////////////////////////////////////////////
+ Implements Extendible<Derived_t>:
+ * Extendible<Derived_t>::Schema
+ * Extendible<Derived_t>::FieldSchema
+ * Extendible<Derived_t>::FieldId<Access_t,Field_t>
+ */
+
+#pragma once
+#include "stdint.h"
+#include <typeinfo>
+#include <typeindex>
+#include <cstddef>
+#include <atomic>
+#include <cstring>
+#include <unordered_map>
+#include <type_traits>
+
+#include "ts/ink_memory.h"
+#include "ts/ink_assert.h"
+#include "AcidPtr.h"
+
+#ifndef ROUNDUP
+#define ROUNDUP(x, y) ((((x) + ((y)-1)) / (y)) * (y))
+#endif
+
+// used for C API
+typedef const void *FieldId_C;
+
+namespace MT // (multi-threaded)
+{
+/// used to store byte offsets to fields
+using ExtendibleOffset_t = uint16_t;
+/// all types must allow unblocking MT read access
+enum AccessEnum { ATOMIC, BIT, STATIC, ACIDPTR, DIRECT, C_API, NUM_ACCESS_TYPES };
+
+inline bool &
+areStaticsFrozen()
+{
+ static bool frozen = 0;
+ return frozen;
+}
+
+/**
+ * @brief Allows code (and Plugins) to declare member variables during system init.
+ *
+ * The size of this structure is actually zero, so it will not change the size of your derived class.
+ * But new and delete are overriden to use allocate enough bytes of the derived type + added fields.
+ * All bool's are packed to save space using the *Bit methods.
+ * This API is focused on thread safe data types that allow minimally blocked reading.
+ * This is templated so static variables are instanced per Derived type. B/c we need to have different
+ * size field sets.
+ *
+ * @tparam Derived_t - the class that you want to extend at runtime.
+ *
+ * @see test_Extendible.cc for examples
+ *
+ */
+template <typename Derived_t> struct Extendible {
+ //////////////////////////////////////////
+ // Internal classes
+ template <AccessEnum FieldAccess_e, typename Field_t> class FieldId; // field handle (strongly type)
+ struct FieldSchema; // field descriptor
+ class Schema; // memory layout, field container
+ // aliases
+ using BitFieldId = FieldId<BIT, bool>;
+
+ //////////////////////////////////////////
+ // Extendible static data
+ /// one schema instance per Derived_t to define contained fields
+ static Schema schema;
+
+ //////////////////////////////////////////
+ // Extendible member variables
+
+ // none
+ // this uses a single alloc and type erasing
+
+ //////////////////////////////////////////
+ // Extendible lifetime management
+ /** don't allow copy construct, that doesn't allow atomicity */
+ Extendible(Extendible &) = delete;
+ /** allocate a new object with additional field data */
+ void *operator new(size_t size);
+ /** construct all fields */
+ Extendible() { schema.call_construct(this_as_char_ptr()); }
+ /** destruct all fields */
+ ~Extendible() { schema.call_destruct(this_as_char_ptr()); }
+
+ //////////////////////////////////////////
+ /// Extendible member methods
+
+ /// ATOMIC API - atomic field reference (read, write or other atomic operation)
+ template <typename Field_t> std::atomic<Field_t> &get(FieldId<ATOMIC, Field_t> const &field);
+
+ /// BIT API - compressed boolean fields
+ bool const get(BitFieldId field) const;
+ bool const readBit(BitFieldId field) const;
+ void writeBit(BitFieldId field, bool const val);
+
+ /// STATIC API - immutable field, value is not expected to change, no internal thread safety
+ template <typename Field_t> Field_t const &get(FieldId<STATIC, Field_t> field) const;
+ template <typename Field_t> Field_t &init(FieldId<STATIC, Field_t> field);
+
+ /// ACIDPTR API - returns a const shared pointer to last committed field value
+ template <typename Field_t> std::shared_ptr<const Field_t> get(FieldId<ACIDPTR, Field_t> field) const;
+ template <typename Field_t> AcidCommitPtr<Field_t> writeAcidPtr(FieldId<ACIDPTR, Field_t> field);
+
+ /// DIRECT API - mutable field, no internal thread safety, expected to be performed externally.
+ template <typename Field_t> Field_t const &get(FieldId<DIRECT, Field_t> field) const;
+ template <typename Field_t> Field_t &get(FieldId<DIRECT, Field_t> field);
+
+ /// C API - returns pointer, no internal thread safety
+ void *get(FieldId_C &field);
+
+ // operator[]
+ template <AccessEnum Access_t, typename Field_t> auto operator[](FieldId<Access_t, Field_t> field) { return get(field); }
+
+ /////////////////////////////////////////////////////////////////////
+ /// defines a runtime "member variable", element of the blob
+ struct FieldSchema {
+ using Func_t = std::function<void(void *)>;
+
+ AccessEnum access = NUM_ACCESS_TYPES; ///< which API is used to access the data
+ std::type_index type = std::type_index(typeid(void)); ///< datatype
+ ExtendibleOffset_t size = 0; ///< size of field
+ ExtendibleOffset_t offset = 0; ///< offset of field from 'this'
+ Func_t construct_fn = nullptr; ///< the data type's constructor
+ Func_t destruct_fn = nullptr; ///< the data type's destructor
+ };
+
+ /////////////////////////////////////////////////////////////////////
+ /// manages the a static layout of fields as data structures
+ class Schema
+ {
+ friend Extendible; // allow direct access for internal classes
+
+ private:
+ std::unordered_map<std::string, FieldSchema> fields; ///< defined elements of the blob by name
+ uint32_t bit_offset = 0; ///< offset to first bit
+ size_t alloc_size = sizeof(Derived_t); ///< bytes to allocate
+ size_t alloc_align = alignof(Derived_t); ///< alignment for each allocation
+ std::atomic_uint instance_count = {0}; ///< the number of Extendible<Derived> instances in use.
+
+ public:
+ Schema() {}
+
+ /// Add a new Field to this record type
+ template <AccessEnum Access_t, typename Field_t>
+ bool addField(FieldId<Access_t, Field_t> &field_id, std::string const &field_name);
+
+ template <typename Field_t> bool addField(FieldId<ACIDPTR, Field_t> &field_id, std::string const &field_name);
+ template <AccessEnum Access_t, typename Field_t> class FieldId<Access_t, Field_t> find(std::string const &field_name);
+
+ /// Add a new Field to this record type (for a C API)
+
+ FieldId_C addField_C(char const *field_name, size_t size, void (*construct_fn)(void *), void (*destruct_fn)(void *));
+ FieldId_C find_C(char const *field_name); ///< C_API returns an existing fieldId
+
+ /// Testing methods
+ size_t size() const; ///< returns sizeof memory allocated
+ bool no_instances() const; ///< returns true if there are no instances of Extendible<Derived_t>
+ bool reset(); ///< clears all field definitions.
+
+ protected:
+ /// Internal methods
+ void updateMemOffsets(); ///< updates memory offsets, alignment, and total allocation size
+ void call_construct(char *ext_as_char_ptr); ///< calls constructor for each field
+ void call_destruct(char *ext_as_char_ptr); ///< call destructor for each field
+
+ }; // end Schema struct
+
+private:
+ // Extendible convience methods
+ char *this_as_char_ptr();
+ char const *this_as_char_ptr() const;
+
+ template <typename Return_t> Return_t at_offset(ExtendibleOffset_t offset);
+ template <typename Return_t> Return_t at_offset(ExtendibleOffset_t offset) const;
+};
+
+// define the static schema per derived type
+template <typename Derived_t> typename Extendible<Derived_t>::Schema Extendible<Derived_t>::schema;
+
+/////////////////////////////////////////////////////////////////////
+// class FieldId
+//
+/// strongly type the FieldId to avoid user error and branching logic
+template <typename Derived_t> template <AccessEnum FieldAccess_e, typename Field_t> class Extendible<Derived_t>::FieldId
+{
+ friend Extendible; // allow direct access for internal classes
+
+private:
+ ExtendibleOffset_t const *offset_ptr = nullptr;
+
+public:
+ FieldId() {}
+ bool
+ isValid() const
+ {
+ return offset_ptr;
+ }
+
+private:
+ FieldId(ExtendibleOffset_t const &offset) { offset_ptr = &offset; }
+ ExtendibleOffset_t
+ offset() const
+ {
+ return *offset_ptr;
+ }
+};
+
+////////////////////////////////////////////////////
+// Extendible::Schema Method Definitions
+//
+
+/// Add a new Field to this record type
+template <typename Derived_t>
+template <AccessEnum Access_t, typename Field_t>
+bool
+Extendible<Derived_t>::Schema::addField(FieldId<Access_t, Field_t> &field_id, std::string const &field_name)
+{
+ static_assert(Access_t == BIT || std::is_same<Field_t, bool>::value == false,
+ "Use BitField so we can pack bits, they are still atomic.");
+ ink_release_assert(instance_count == 0); // it's too late, we already started allocating.
+
+ ExtendibleOffset_t size = 0;
+ switch (Access_t) {
+ case BIT: {
+ size = 0;
+ } break;
+ case ATOMIC: {
+ size = std::max(sizeof(std::atomic<Field_t>), alignof(std::atomic<Field_t>));
+ alloc_align = std::max(alloc_align, alignof(std::atomic<Field_t>));
+ } break;
+ default:
+ size = sizeof(Field_t);
+ }
+
+ // capture the default constructors of the data type
+ static auto construct_fn = [](void *ptr) { new (ptr) Field_t; };
+ static auto destruct_fn = [](void *ptr) { static_cast<Field_t *>(ptr)->~Field_t(); };
+
+ fields[field_name] = FieldSchema{Access_t, std::type_index(typeid(Field_t)), size, 0, construct_fn, destruct_fn};
+ field_id.offset_ptr = &fields[field_name].offset;
+ updateMemOffsets();
+ return true;
+}
+
+/// Add a new Field to this record type
+template <typename Derived_t>
+template <typename Field_t>
+bool
+Extendible<Derived_t>::Schema::addField(FieldId<ACIDPTR, Field_t> &field_id, std::string const &field_name)
+{
+ static_assert(std::is_copy_constructible<Field_t>::value == true, "Must have a copy constructor to use AcidPtr.");
+ ink_release_assert(instance_count == 0); // it's too late, we already started allocating.
+ using ptr_t = AcidPtr<Field_t>;
+ ExtendibleOffset_t size = sizeof(ptr_t);
+
+ // capture the default constructors of the data type
+ static auto construct_fn = [](void *ptr) { new (ptr) ptr_t(new Field_t()); };
+ static auto destruct_fn = [](void *ptr) { static_cast<ptr_t *>(ptr)->~ptr_t(); };
+
+ fields[field_name] = FieldSchema{ACIDPTR, std::type_index(typeid(Field_t)), size, 0, construct_fn, destruct_fn};
+ field_id.offset_ptr = &fields[field_name].offset;
+ updateMemOffsets();
+ return true;
+}
+
+/// Add a new Field to this record type (for a C API)
+template <typename Derived_t>
+FieldId_C
+Extendible<Derived_t>::Schema::addField_C(char const *field_name, size_t size, void (*construct_fn)(void *),
+ void (*destruct_fn)(void *))
+{
+ ink_release_assert(size == 1 || size == 2 || size == 4 || size % 8 == 0); // must use aligned sizes
+ ink_release_assert(instance_count == 0); // it's too late, we already started allocating.
+ const std::string field_name_str(field_name);
+ fields[field_name_str] =
+ FieldSchema{C_API, std::type_index(typeid(void *)), static_cast<ExtendibleOffset_t>(size), 0, construct_fn, destruct_fn};
+ updateMemOffsets();
+ return &fields[field_name].offset;
+}
+
+template <typename Derived_t>
+template <AccessEnum Access_t, typename Field_t>
+class Extendible<Derived_t>::FieldId<Access_t, Field_t>
+Extendible<Derived_t>::Schema::find(std::string const &field_name)
+{
+ auto field_iter = fields.find(field_name);
+ if (field_iter == fields.end()) {
+ return Extendible<Derived_t>::FieldId<Access_t, Field_t>(); // didn't find name
+ }
+ FieldSchema &fs = field_iter->second; // found name
+ ink_assert(fs.access == Access_t); // conflicting access, between field add and find
+ ink_assert(fs.type == std::type_index(typeid(Field_t))); // conflicting type, between field add and find
+ return Extendible<Derived_t>::FieldId<Access_t, Field_t>(fs.offset);
+}
+
+template <typename Derived_t>
+FieldId_C
+Extendible<Derived_t>::Schema::find_C(char const *field_name)
+{
+ auto field_iter = fields.find(field_name);
+ ink_release_assert(field_iter != fields.end());
+ FieldSchema &fs = field_iter->second;
+ ink_release_assert(fs.access == C_API);
+ return &fs.offset;
+}
+
+template <typename Derived_t>
+void
+Extendible<Derived_t>::Schema::updateMemOffsets()
+{
+ ink_release_assert(instance_count == 0);
+
+ uint32_t acc_offset = ROUNDUP(sizeof(Derived_t), alloc_align);
+
+ ExtendibleOffset_t size_blocks[] = {4, 2, 1};
+
+ for (auto &pair_fld : fields) {
+ auto &fld = pair_fld.second;
+ if (fld.size >= 8) {
+ fld.offset = acc_offset;
+ acc_offset += fld.size;
+ }
+ }
+ for (auto sz : size_blocks) {
+ for (auto &pair_fld : fields) {
+ auto &fld = pair_fld.second;
+ if (fld.size == sz) {
+ fld.offset = acc_offset;
+ acc_offset += fld.size;
+ }
+ }
+ }
+ bit_offset = acc_offset;
+ uint32_t acc_bit_offset = 0;
+ for (auto &pair_fld : fields) {
+ auto &fld = pair_fld.second;
+ if (fld.size == 0) {
+ fld.offset = acc_bit_offset;
+ ++acc_bit_offset;
+ }
+ }
+
+ alloc_size = acc_offset + (acc_bit_offset + 7) / 8; // size '0' are packed bit allocations.
+}
+
+template <typename Derived_t>
+bool
+Extendible<Derived_t>::Schema::reset()
+{
+ if (instance_count > 0) {
+ // free instances before calling this so we don't leak memory
+ return false;
+ }
+ fields.clear();
+ alloc_size = sizeof(Derived_t);
+ alloc_align = alignof(Derived_t);
+ return true;
+}
+
+template <typename Derived_t>
+void
+Extendible<Derived_t>::Schema::call_construct(char *ext_as_char_ptr)
+{
+ ++instance_count; // don't allow schema modification
+ // init all extendible memory to 0, incase constructors don't
+ memset(ext_as_char_ptr + sizeof(Derived_t), 0, alloc_size - sizeof(Derived_t));
+
+ for (auto const &elm : fields) {
+ FieldSchema const &field_schema = elm.second;
+ if (field_schema.access != BIT && field_schema.construct_fn != nullptr) {
+ field_schema.construct_fn(ext_as_char_ptr + field_schema.offset);
+ }
+ }
+}
+
+template <typename Derived_t>
+void
+Extendible<Derived_t>::Schema::call_destruct(char *ext_as_char_ptr)
+{
+ for (auto const &elm : fields) {
+ FieldSchema const &field_schema = elm.second;
+ if (field_schema.access != BIT && field_schema.destruct_fn != nullptr) {
+ field_schema.destruct_fn(ext_as_char_ptr + field_schema.offset);
+ }
+ }
+ --instance_count;
+}
+
+template <typename Derived_t>
+size_t
+Extendible<Derived_t>::Schema::size() const
+{
+ return alloc_size;
+}
+
+template <typename Derived_t>
+bool
+Extendible<Derived_t>::Schema::no_instances() const
+{
+ return instance_count == 0;
+}
+
+////////////////////////////////////////////////////
+// Extendible Method Definitions
+//
+
+/// return a reference to an atomic field (read, write or other atomic operation)
+template <typename Derived_t>
+template <typename Field_t>
+std::atomic<Field_t> &
+Extendible<Derived_t>::get(FieldId<ATOMIC, Field_t> const &field)
+{
+ return *at_offset<std::atomic<Field_t> *>(field.offset());
+}
+
+/// atomically read a bit value
+template <typename Derived_t>
+bool const
+Extendible<Derived_t>::get(BitFieldId field) const
+{
+ return readBit(field);
+}
+
+/// atomically read a bit value
+template <typename Derived_t>
+bool const
+Extendible<Derived_t>::readBit(BitFieldId field) const
+{
+ const char &c = *(at_offset<char const *>(schema.bit_offset) + field.offset() / 8);
+ const char mask = 1 << (field.offset() % 8);
+ return (c & mask) != 0;
+}
+
+/// atomically write a bit value
+template <typename Derived_t>
+void
+Extendible<Derived_t>::writeBit(BitFieldId field, bool const val)
+{
+ char &c = *(at_offset<char *>(schema.bit_offset) + field.offset() / 8);
+ const char mask = 1 << (field.offset() % 8);
+ if (val) {
+ c |= mask;
+ } else {
+ c &= ~mask;
+ }
+}
+
+/// return a reference to an const field
+template <typename Derived_t>
+template <typename Field_t>
+Field_t const & // value is not expected to change, or be freed while 'this' exists.
+Extendible<Derived_t>::get(FieldId<STATIC, Field_t> field) const
+{
+ return *at_offset<const Field_t *>(field.offset());
+}
+
+/// return a reference to an static field that is non-const for initialization purposes
+template <typename Derived_t>
+template <typename Field_t>
+Field_t &
+Extendible<Derived_t>::init(FieldId<STATIC, Field_t> field)
+{
+ ink_release_assert(!areStaticsFrozen());
+ return *at_offset<Field_t *>(field.offset());
+}
+
+/// return a shared pointer to last committed field value
+template <typename Derived_t>
+template <typename Field_t>
+std::shared_ptr<const Field_t> // shared_ptr so the value can be updated while in use.
+Extendible<Derived_t>::get(FieldId<ACIDPTR, Field_t> field) const
+{
+ const AcidPtr<Field_t> &reader = *at_offset<const AcidPtr<Field_t> *>(field.offset());
+ return reader.getPtr();
+}
+
+/// return a writer created from the last committed field value
+template <typename Derived_t>
+template <typename Field_t>
+AcidCommitPtr<Field_t>
+Extendible<Derived_t>::writeAcidPtr(FieldId<ACIDPTR, Field_t> field)
+{
+ AcidPtr<Field_t> &reader = *at_offset<AcidPtr<Field_t> *>(field.offset());
+ return AcidCommitPtr<Field_t>(reader);
+}
+
+/// return a reference to a field, without concurrent access protection
+template <typename Derived_t>
+template <typename Field_t>
+Field_t & // value is not expected to change, or be freed while 'this' exists.
+Extendible<Derived_t>::get(FieldId<DIRECT, Field_t> field)
+{
+ return *at_offset<Field_t *>(field.offset());
+}
+
+/// return a const reference to a field, without concurrent access protection
+template <typename Derived_t>
+template <typename Field_t>
+Field_t const & // value is not expected to change, or be freed while 'this' exists.
+Extendible<Derived_t>::get(FieldId<DIRECT, Field_t> field) const
+{
+ return *at_offset<const Field_t *>(field.offset());
+}
+
+/// C API
+template <typename Derived_t>
+void *
+Extendible<Derived_t>::get(FieldId_C &field)
+{
+ return at_offset<void *>(*static_cast<ExtendibleOffset_t const *>(field));
+}
+
+/// allocate a new object with properties
+template <class Derived_t>
+void *
+Extendible<Derived_t>::operator new(size_t size)
+{
+ // allocate one block for all the memory, including the derived_t members
+ // return ::operator new(schema.alloc_size);
+ void *ptr = ats_memalign(schema.alloc_align, schema.alloc_size);
+ ink_release_assert(ptr != nullptr);
+ return ptr;
+}
+
+// private
+template <class Derived_t>
+char *
+Extendible<Derived_t>::this_as_char_ptr()
+{
+ return static_cast<char *>(static_cast<void *>(this));
+}
+// private
+template <class Derived_t>
+char const *
+Extendible<Derived_t>::this_as_char_ptr() const
+{
+ return static_cast<char const *>(static_cast<void const *>(this));
+}
+// private
+template <class Derived_t>
+template <typename Return_t>
+Return_t
+Extendible<Derived_t>::at_offset(ExtendibleOffset_t offset)
+{
+ return reinterpret_cast<Return_t>(this_as_char_ptr() + offset);
+}
+// private
+template <class Derived_t>
+template <typename Return_t>
+Return_t
+Extendible<Derived_t>::at_offset(ExtendibleOffset_t offset) const
+{
+ return reinterpret_cast<Return_t>(this_as_char_ptr() + offset);
+}
+
+// TODO: override std::get<field_t>(Extendible &)
+
+}; // namespace MT
diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am
index ef44472..f36b85d 100644
--- a/lib/ts/Makefile.am
+++ b/lib/ts/Makefile.am
@@ -52,6 +52,8 @@ libtsutil_la_LIBADD = \
libtsutil_la_SOURCES = \
Allocator.h \
+ AcidPtr.cc \
+ AcidPtr.h \
Arena.cc \
Arena.h \
BaseLogFile.cc \
@@ -73,6 +75,7 @@ libtsutil_la_SOURCES = \
DynArray.h \
EventNotify.cc \
EventNotify.h \
+ Extendible.h \
fastlz.c \
fastlz.h \
Hash.cc \
@@ -259,13 +262,14 @@ test_tsutil_SOURCES = \
test_tslib_CPPFLAGS = $(AM_CPPFLAGS)\
-I$(abs_top_srcdir)/tests/include
-# add you catch based test file here for tslib
test_tslib_CXXFLAGS = -Wno-array-bounds $(AM_CXXFLAGS)
test_tslib_LDADD = libtsutil.la $(top_builddir)/iocore/eventsystem/libinkevent.a
test_tslib_SOURCES = \
unit-tests/unit_test_main.cc \
+ unit-tests/test_AcidPtr.cc \
unit-tests/test_BufferWriter.cc \
unit-tests/test_BufferWriterFormat.cc \
+ unit-tests/test_Extendible.cc \
unit-tests/test_History.cc \
unit-tests/test_ink_inet.cc \
unit-tests/test_IntrusiveDList.cc \
diff --git a/lib/ts/unit-tests/test_AcidPtr.cc b/lib/ts/unit-tests/test_AcidPtr.cc
new file mode 100644
index 0000000..baa3a9b
--- /dev/null
+++ b/lib/ts/unit-tests/test_AcidPtr.cc
@@ -0,0 +1,96 @@
+/** @file
+ Test file for Extendible
+ @section license License
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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 REQUIRE 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.
+ */
+
+#include "catch.hpp"
+
+#include "ts/AcidPtr.h"
+#include <iostream>
+#include <string>
+#include <vector>
+#include <ctime>
+#include <thread>
+#include <atomic>
+
+using namespace std;
+
+TEST_CASE("AcidPtr Atomicity")
+{
+ // fail if skew is detected.
+ const int N = 1000;
+ AcidPtr<vector<int>> ptr(new vector<int>(50));
+ std::thread workers[N];
+ atomic<int> errors = {0};
+
+ auto job_read_write = [&ptr, &errors]() {
+ int r = rand();
+ AcidCommitPtr<vector<int>> cptr(ptr);
+ int old = (*cptr)[0];
+ for (int &i : *cptr) {
+ if (i != old) {
+ errors++;
+ }
+ i = r;
+ }
+ };
+ auto job_read = [&ptr, &errors]() {
+ auto sptr = ptr.getPtr();
+ int old = (*sptr)[0];
+ for (int const &i : *sptr) {
+ if (i != old) {
+ errors++;
+ }
+ }
+ };
+
+ std::thread writers[N];
+ std::thread readers[N];
+
+ for (int i = 0; i < N; i++) {
+ writers[i] = std::thread(job_read_write);
+ readers[i] = std::thread(job_read);
+ }
+
+ for (int i = 0; i < N; i++) {
+ writers[i].join();
+ readers[i].join();
+ }
+ REQUIRE(errors == 0); // skew detected
+}
+
+TEST_CASE("AcidPtr Isolation")
+{
+ AcidPtr<int> p;
+ REQUIRE(p.getPtr() != nullptr);
+ REQUIRE(p.getPtr().get() != nullptr);
+ {
+ AcidCommitPtr<int> w(p);
+ *w = 40;
+ }
+ CHECK(*p.getPtr() == 40);
+ {
+ AcidCommitPtr<int> w = p;
+ *w += 1;
+ CHECK(*p.getPtr() == 40); // new value not commited until end of scope
+ }
+ CHECK(*p.getPtr() == 41);
+ {
+ *AcidCommitPtr<int>(p) += 1; // leaves scope immediately if not named.
+ CHECK(*p.getPtr() == 42);
+ }
+ CHECK(*p.getPtr() == 42);
+}
diff --git a/lib/ts/unit-tests/test_Extendible.cc b/lib/ts/unit-tests/test_Extendible.cc
new file mode 100644
index 0000000..812e15e
--- /dev/null
+++ b/lib/ts/unit-tests/test_Extendible.cc
@@ -0,0 +1,286 @@
+/** @file
+ Test file for Extendible
+ @section license License
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you 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 REQUIRE 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.
+ */
+
+#include "catch.hpp"
+
+#include "ts/Extendible.h"
+#include <iostream>
+#include <string>
+#include <vector>
+#include <ctime>
+#include <thread>
+#include "ts/ink_atomic.h"
+
+using namespace std;
+using namespace MT;
+
+// Extendible is abstract and must be derived in a CRTP
+struct Derived : Extendible<Derived> {
+ string m_str;
+};
+
+// something to store more complex than an int
+struct testField {
+ uint8_t arr[5];
+ static int alive;
+ testField()
+ {
+ uint8_t x = 1;
+ for (uint8_t &a : arr) {
+ a = x;
+ x *= 2;
+ }
+ alive++;
+ }
+ ~testField()
+ {
+ for (uint8_t &a : arr) {
+ a = 0;
+ }
+ alive--;
+ }
+};
+int testField::alive = 0;
+
+TEST_CASE("Extendible", "")
+{
+ typename Derived::BitFieldId bit_a, bit_b, bit_c;
+ typename Derived::FieldId<ATOMIC, int> int_a, int_b, int_c;
+ Derived *ptr;
+
+ // test cases:
+ //[constructor] [operator] [type] [access] [capacity] [modifier] [operation] [compare] [find]
+ // I don't use INFOS because this modifies static variables many times, is not thread safe.
+ INFO("Extendible()")
+ {
+ ptr = new Derived();
+ REQUIRE(ptr != nullptr);
+ }
+
+ INFO("~Extendible")
+ {
+ //
+ delete ptr;
+ }
+
+ INFO("Schema Reset")
+ {
+ ptr = new Derived();
+ REQUIRE(Derived::schema.reset() == false);
+ delete ptr;
+ REQUIRE(Derived::schema.reset() == true);
+ }
+
+ INFO("shared_ptr")
+ {
+ shared_ptr<Derived> sptr(new Derived());
+ REQUIRE(sptr);
+ }
+
+ INFO("add a bit field")
+ {
+ //
+ REQUIRE(Derived::schema.addField(bit_a, "bit_a"));
+ }
+
+ INFO("test bit field")
+ {
+ shared_ptr<Derived> sptr(new Derived());
+ auto &ref = *sptr;
+ ref.writeBit(bit_a, 1);
+ CHECK(ref[bit_a] == 1);
+ }
+
+ INFO("test bit packing")
+ {
+ REQUIRE(Derived::schema.reset() == true);
+ CHECK(Derived::schema.size() == sizeof(std::string));
+
+ REQUIRE(Derived::schema.addField(bit_a, "bit_a"));
+ CHECK(Derived::schema.size() == sizeof(std::string) + 1);
+ REQUIRE(Derived::schema.addField(bit_b, "bit_b"));
+ CHECK(Derived::schema.size() == sizeof(std::string) + 1);
+ REQUIRE(Derived::schema.addField(bit_c, "bit_c"));
+ CHECK(Derived::schema.size() == sizeof(std::string) + 1);
+
+ shared_ptr<Derived> sptr(new Derived());
+ Derived &ref = *sptr;
+ ref.writeBit(bit_a, true);
+ ref.writeBit(bit_b, false);
+ ref.writeBit(bit_c, true);
+ CHECK(ref[bit_a] == true);
+ CHECK(ref[bit_b] == false);
+ CHECK(ref[bit_c] == true);
+ }
+
+ INFO("store int field")
+ {
+ REQUIRE(Derived::schema.addField(int_a, "int_a"));
+ REQUIRE(Derived::schema.addField(int_b, "int_b"));
+ REQUIRE(Derived::schema.size() == sizeof(std::string) + 1 + sizeof(std::atomic_int) * 2);
+
+ shared_ptr<Derived> sptr(new Derived());
+ Derived &ref = *sptr;
+ CHECK(ref.get(int_a) == 0);
+ CHECK(ref.get(int_b) == 0);
+ ++ref.get(int_a);
+ ref.get(int_b) = 42;
+ ref.m_str = "Hello";
+ CHECK(ref.get(int_a) == 1);
+ CHECK(ref.get(int_b) == 42);
+ CHECK(ref.m_str == "Hello");
+ }
+
+ INFO("C API add int field")
+ {
+ FieldId_C cf_a = Derived::schema.addField_C("cf_a", 4, nullptr, nullptr);
+ CHECK(Derived::schema.size() == sizeof(std::string) + 1 + sizeof(std::atomic_int) * 2 + 4);
+ CHECK(Derived::schema.find_C("cf_a") == cf_a);
+ }
+
+ INFO("C API alloc instance")
+ {
+ shared_ptr<Derived> sptr(new Derived());
+ CHECK(sptr.get() != nullptr);
+ }
+
+ INFO("C API test int field")
+ {
+ shared_ptr<Derived> sptr(new Derived());
+ Derived &ref = *sptr;
+ FieldId_C cf_a = Derived::schema.find_C("cf_a");
+ uint8_t *data8 = (uint8_t *)ref.get(cf_a);
+ CHECK(data8[0] == 0);
+ ink_atomic_increment(data8, 1);
+ *(data8 + 1) = 5;
+ *(data8 + 2) = 7;
+
+ ref.m_str = "Hello";
+
+ uint32_t *data32 = (uint32_t *)ref.get(cf_a);
+ CHECK(*data32 == 0x00070501);
+ CHECK(ref.m_str == "Hello");
+ }
+
+ Derived::FieldId<ACIDPTR, testField> tf_a;
+ INFO("ACIDPTR add field")
+ {
+ REQUIRE(Derived::schema.addField(tf_a, "tf_a"));
+ CHECK(Derived::schema.size() == sizeof(std::string) + 1 + sizeof(std::atomic_int) * 2 + 4 + sizeof(std::shared_ptr<testField>));
+ REQUIRE(Derived::schema.find<ACIDPTR, testField>("tf_a").isValid());
+ }
+
+ INFO("ACIDPTR test")
+ {
+ shared_ptr<Derived> sptr(new Derived());
+ Derived &ref = *sptr;
+ // ref.m_str = "Hello";
+ auto tf_a = Derived::schema.find<ACIDPTR, testField>("tf_a");
+ {
+ std::shared_ptr<const testField> tf_a_sptr = ref.get(tf_a);
+ const testField &dv = *tf_a_sptr;
+ CHECK(dv.arr[0] == 1);
+ CHECK(dv.arr[1] == 2);
+ CHECK(dv.arr[2] == 4);
+ CHECK(dv.arr[3] == 8);
+ CHECK(dv.arr[4] == 16);
+ }
+ CHECK(testField::alive == 1);
+ }
+
+ INFO("ACIDPTR destroyed")
+ {
+ //
+ CHECK(testField::alive == 0);
+ }
+
+ INFO("AcidPtr AcidCommitPtr casting");
+ {
+ void *mem = malloc(sizeof(AcidPtr<testField>));
+ new (mem) AcidPtr<testField>();
+ AcidPtr<testField> &reader = *static_cast<AcidPtr<testField> *>(mem);
+ {
+ AcidCommitPtr<testField> writer = AcidCommitPtr<testField>(reader);
+ CHECK(writer->arr[0] == 1);
+ CHECK(reader.getPtr()->arr[0] == 1);
+ writer->arr[0] = 99;
+ CHECK(writer->arr[0] == 99);
+ CHECK(reader.getPtr()->arr[0] == 1);
+ }
+ CHECK(reader.getPtr()->arr[0] == 99);
+ free(mem);
+ }
+ INFO("ACIDPTR block-free reader")
+ {
+ auto tf_a = Derived::schema.find<ACIDPTR, testField>("tf_a");
+ REQUIRE(tf_a.isValid());
+ Derived &d = *(new Derived());
+ CHECK(d.get(tf_a)->arr[0] == 1);
+ { // write 0
+ AcidCommitPtr<testField> w = d.writeAcidPtr(tf_a);
+ REQUIRE(w != nullptr);
+ REQUIRE(w.get() != nullptr);
+ w->arr[0] = 0;
+ }
+ // read 0
+ CHECK(d.get(tf_a)->arr[0] == 0);
+ // write 1 and read 0
+ {
+ AcidCommitPtr<testField> tf_a_wtr = d.writeAcidPtr(tf_a);
+ tf_a_wtr->arr[0] = 1;
+ CHECK(d.get(tf_a)->arr[0] == 0);
+ // [end of scope] write is committed
+ }
+ // read 1
+ CHECK(d.get(tf_a)->arr[0] == 1);
+ delete &d;
+ }
+
+ INFO("STATIC")
+ {
+ typename Derived::FieldId<STATIC, int> tf_d;
+ Derived::schema.addField(tf_d, "tf_d");
+ REQUIRE(tf_d.isValid());
+ Derived &d = *(new Derived());
+ d.init(tf_d) = 5;
+ areStaticsFrozen() = true;
+
+ CHECK(d.get(tf_d) == 5);
+
+ // this asserts when areStaticsFrozen() = true
+ // CHECK(d.init(tf_d) == 5);
+ delete &d;
+ }
+
+ INFO("DIRECT")
+ {
+ typename Derived::FieldId<DIRECT, int> tf_e;
+ Derived::schema.addField(tf_e, "tf_e");
+ REQUIRE(tf_e.isValid());
+ Derived &d = *(new Derived());
+ d.get(tf_e) = 5;
+
+ CHECK(d.get(tf_e) == 5);
+
+ // this asserts when areStaticsFrozen() = true
+ // CHECK(d.init(tf_e) == 5);
+ delete &d;
+ }
+
+ INFO("Extendible Test Complete")
+}