| // 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. |
| |
| |
| #ifndef IMPALA_RUNTIME_TUPLE_H |
| #define IMPALA_RUNTIME_TUPLE_H |
| |
| #include "codegen/impala-ir.h" |
| #include "common/logging.h" |
| #include "gutil/macros.h" |
| #include "runtime/descriptors.h" |
| #include "runtime/mem-pool.h" |
| #include "util/ubsan.h" |
| |
| namespace llvm { |
| class Function; |
| class Constant; |
| } |
| |
| namespace impala { |
| |
| struct CollectionValue; |
| struct StringValue; |
| class TupleDescriptor; |
| class TupleRow; |
| |
| /// Minimal struct to hold slot offset information from a SlotDescriptor. Designed |
| /// to simplify constant substitution in CodegenCopyStrings() and allow more efficient |
| /// interpretation in CopyStrings(). |
| struct SlotOffsets { |
| NullIndicatorOffset null_indicator_offset; |
| int tuple_offset; |
| |
| /// Generate an LLVM Constant containing the offset values of this SlotOffsets instance. |
| /// Needs to be updated if the layout of this struct changes. |
| llvm::Constant* ToIR(LlvmCodeGen* codegen) const; |
| |
| static const char* LLVM_CLASS_NAME; |
| }; |
| |
| /// A tuple is stored as a contiguous sequence of bytes containing a fixed number |
| /// of fixed-size slots along with a bit vector containing null indicators |
| /// for each nullable slots. The layout of a tuple is computed by the planner and |
| /// represented in a TupleDescriptor. A tuple has a "packed" memory layout - the |
| /// start of the tuple can have any alignment and slots within the tuple are not |
| /// necessarily aligned. |
| /// |
| /// Tuples are handled as untyped memory throughout much of the runtime, with that |
| /// memory reinterpreted as the appropriate slot types when needed. This Tuple class |
| /// (which is a zero-length class with no members) provides a convenient abstraction |
| /// over this untyped memory for common operations. The untyped tuple memory can be |
| /// cast to a Tuple* in order to use the functions below. |
| /// |
| /// NULL and zero-length Tuples |
| /// =========================== |
| /// Tuples can be logically NULL in some cases to indicate that all slots in the |
| /// tuple are NULL. This occurs in rows produced by an outer join where a matching |
| /// tuple was not found on one side of the join. In some plans the distinction between |
| /// a NULL tuple and a non-NULL tuple with all NULL slots is significant and used by |
| /// the planner via TupleIsNulLPredicate() to correctly place predicates at certain |
| /// places in the plan. |
| /// |
| /// A tuple with 0 materialised slots is either represented as an arbitrary non-NULL |
| /// pointer (e.g. POISON), if the tuple is logically non-NULL or as a NULL pointer |
| /// if the tuple is logically NULL. |
| /// |
| /// TODO: Our projection of collection-typed slots breaks/augments the conventional |
| /// semantics of the null bits, because we rely on producers of array values to also |
| /// set the slot value in addition to the null bit. We should address this issue with |
| /// a proper projection that restores the intended (original) null bit semantics. |
| /// See also UnnestNode for details on the projection. |
| class Tuple { |
| public: |
| /// initialize individual tuple with data residing in mem pool |
| static Tuple* Create(int size, MemPool* pool) { |
| if (size == 0) return NULL; |
| Tuple* result = reinterpret_cast<Tuple*>(pool->Allocate(size)); |
| result->Init(size); |
| return result; |
| } |
| |
| /// Pointer that marks an invalid Tuple address. Rather than leaving Tuple |
| /// pointers uninitialized, they should point to the value of POISON. |
| static Tuple* const POISON; |
| |
| void Init(int size) { memset(this, 0, size); } |
| |
| void ClearNullBits(const TupleDescriptor& tuple_desc) { |
| ClearNullBits(tuple_desc.null_bytes_offset(), tuple_desc.num_null_bytes()); |
| } |
| |
| static void ClearNullBits(Tuple* that, int null_bytes_offset, int num_null_bytes) { |
| if (that != nullptr) that->ClearNullBits(null_bytes_offset, num_null_bytes); |
| } |
| |
| void ClearNullBits(int null_bytes_offset, int num_null_bytes) { |
| Ubsan::MemSet( |
| reinterpret_cast<uint8_t*>(this) + null_bytes_offset, 0, num_null_bytes); |
| } |
| |
| /// The total size of all data represented in this tuple (tuple data and referenced |
| /// string and collection data). |
| int64_t TotalByteSize(const TupleDescriptor& desc) const; |
| |
| /// The size of all referenced string and collection data. |
| int64_t VarlenByteSize(const TupleDescriptor& desc) const; |
| |
| /// Create a copy of 'this', including all of its referenced variable-length data |
| /// (i.e. strings and collections), using pool to allocate memory. Returns the copy. |
| Tuple* DeepCopy(const TupleDescriptor& desc, MemPool* pool); |
| |
| /// Create a copy of 'this', including all its referenced variable-length data |
| /// (i.e. strings and collections), using pool to allocate memory. This version does |
| /// not allocate a tuple, instead copying to 'dst'. 'dst' must already be allocated to |
| /// the correct size (i.e. TotalByteSize()). |
| void DeepCopy(Tuple* dst, const TupleDescriptor& desc, MemPool* pool); |
| |
| /// Create a copy of 'this', including all referenced variable-length data (i.e. strings |
| /// and collections), into 'data'. The tuple is written first, followed by any |
| /// variable-length data. 'data' and 'offset' will be incremented by the total number of |
| /// bytes written. 'data' must already be allocated to the correct size |
| /// (i.e. TotalByteSize()). |
| /// If 'convert_ptrs' is true, rewrites pointers that are part of the tuple as offsets |
| /// into 'data'. Otherwise they will remain pointers directly into data. The offsets are |
| /// determined by 'offset', where '*offset' corresponds to address '*data'. |
| void DeepCopy(const TupleDescriptor& desc, char** data, int* offset, |
| bool convert_ptrs = false); |
| |
| /// This function should only be called on tuples created by DeepCopy() with |
| /// 'convert_ptrs' = true. It takes all pointers contained in this tuple (i.e. in |
| /// StringValues and CollectionValues, including those contained within other |
| /// CollectionValues), and converts the offset values into pointers into |
| /// 'tuple_data'. 'tuple_data' should be the serialized tuple buffer created by |
| /// DeepCopy(). Note that 'tuple_data' should always be the beginning of this buffer, |
| /// regardless of this tuple's offset in 'tuple_data'. |
| void ConvertOffsetsToPointers(const TupleDescriptor& desc, uint8_t* tuple_data); |
| |
| /// Materialize 'this' by evaluating the expressions in 'materialize_exprs_ctxs' over |
| /// the specified 'row'. |
| /// |
| /// If non-NULL, 'pool' is used to allocate var-length data, otherwise var-length data |
| /// isn't copied. (Memory for this tuple itself must already be allocated.) 'NULL_POOL' |
| /// must be true if 'pool' is NULL and false otherwise. The template parameter serves |
| /// only to differentiate the NULL vs. non-NULL pool cases when we replace the function |
| /// calls during codegen; the parameter means there are two different function symbols. |
| /// Callers of CodegenMaterializeExprs must set 'use_mem_pool' to true to generate the |
| /// IR function for the case 'pool' is non-NULL and false for the NULL pool case. |
| /// |
| /// If 'COLLECT_STRING_VALS' is true, the materialized non-NULL string value slots and |
| /// the total length of the string slots are returned in 'non_null_string_values' and |
| /// 'total_string_lengths'. 'non_null_string_values' and 'total_string_lengths' must be |
| /// non-NULL in this case. 'non_null_string_values' does not need to be empty; its |
| /// original contents will be overwritten. |
| /// TODO: this function does not collect other var-len types such as collections. |
| template <bool COLLECT_STRING_VALS, bool NULL_POOL> |
| inline void IR_ALWAYS_INLINE MaterializeExprs(TupleRow* row, |
| const TupleDescriptor& desc, const std::vector<ScalarExprEvaluator*>& evals, |
| MemPool* pool, std::vector<StringValue*>* non_null_string_values = NULL, |
| int* total_string_lengths = NULL) { |
| DCHECK_EQ(NULL_POOL, pool == NULL); |
| DCHECK_EQ(evals.size(), desc.slots().size()); |
| StringValue** non_null_string_values_array = NULL; |
| int num_non_null_string_values = 0; |
| if (COLLECT_STRING_VALS) { |
| DCHECK(non_null_string_values != NULL); |
| DCHECK(total_string_lengths != NULL); |
| // string::resize() will zero-initialize any new values, so we resize to the largest |
| // possible size here, then truncate the vector below once we know the actual size |
| // (which preserves already-written values). |
| non_null_string_values->resize(desc.string_slots().size()); |
| non_null_string_values_array = non_null_string_values->data(); |
| *total_string_lengths = 0; |
| } |
| MaterializeExprs<COLLECT_STRING_VALS, NULL_POOL>(row, desc, |
| evals.data(), pool, non_null_string_values_array, |
| total_string_lengths, &num_non_null_string_values); |
| if (COLLECT_STRING_VALS) non_null_string_values->resize(num_non_null_string_values); |
| } |
| |
| /// Copy the var-len string data in this tuple into the provided memory pool and update |
| /// the string slots to point at the copied strings. 'string_slot_offsets' contains the |
| /// required offsets in a contiguous array to allow efficient iteration and easy |
| /// substitution of the array with constants for codegen. 'err_ctx' is a string that is |
| /// included in error messages to provide context. Returns true on success, otherwise on |
| /// failure sets 'status' to an error. This odd return convention is used to avoid |
| /// emitting unnecessary code for ~Status() in perf-critical code. |
| bool CopyStrings(const char* err_ctx, RuntimeState* state, |
| const SlotOffsets* string_slot_offsets, int num_string_slots, MemPool* pool, |
| Status* status) noexcept; |
| |
| /// Symbols (or substrings of the symbols) of MaterializeExprs(). These can be passed to |
| /// LlvmCodeGen::ReplaceCallSites(). |
| static const char* MATERIALIZE_EXPRS_SYMBOL; |
| static const char* MATERIALIZE_EXPRS_NULL_POOL_SYMBOL; |
| |
| /// Generates an IR version of MaterializeExprs(), returned in 'fn'. Currently only |
| /// 'collect_string_vals' = false is implemented and some arguments passed to the IR |
| /// function are unused. |
| /// |
| /// If 'use_mem_pool' is true, any varlen data will be copied into the MemPool specified |
| /// in the 'pool' argument of the generated function. Otherwise, the varlen data won't |
| /// be copied. There are two different MaterializeExprs symbols to differentiate between |
| /// these cases when we replace the function calls during codegen. Please see comment |
| /// of MaterializeExprs() for details. |
| static Status CodegenMaterializeExprs(LlvmCodeGen* codegen, bool collect_string_vals, |
| const TupleDescriptor& desc, const vector<ScalarExpr*>& slot_materialize_exprs, |
| bool use_mem_pool, llvm::Function** fn); |
| |
| /// Generates an IR version of CopyStrings(). The offsets of string slots are replaced |
| /// with constants. This can allow the LLVM optimiser to unroll the loop and generate |
| /// efficient code without interpretation overhead. The LLVM optimiser at -O2 generally |
| /// will only unroll the loop for small numbers of iterations: 8 or less in some |
| /// experiements. On success, 'fn' is set to point to the generated function. |
| static Status CodegenCopyStrings(LlvmCodeGen* codegen, |
| const TupleDescriptor& desc, llvm::Function** materialize_strings_fn); |
| |
| /// Turn null indicator bit on. For non-nullable slots, the mask will be 0 and |
| /// this is a no-op (but we don't have to branch to check is slots are nullable). |
| void SetNull(const NullIndicatorOffset& offset) { |
| char* null_indicator_byte = reinterpret_cast<char*>(this) + offset.byte_offset; |
| *null_indicator_byte |= offset.bit_mask; |
| } |
| |
| /// Turn null indicator bit off. |
| void SetNotNull(const NullIndicatorOffset& offset) { |
| char* null_indicator_byte = reinterpret_cast<char*>(this) + offset.byte_offset; |
| *null_indicator_byte &= ~offset.bit_mask; |
| } |
| |
| bool IsNull(const NullIndicatorOffset& offset) const { |
| const char* null_indicator_byte = |
| reinterpret_cast<const char*>(this) + offset.byte_offset; |
| return (*null_indicator_byte & offset.bit_mask) != 0; |
| } |
| |
| /// Set the null indicators on 'num_tuples' tuples. The first tuple is stored at |
| /// 'tuple_mem' and subsequent tuples must be stored at a stride of 'tuple_stride' |
| /// bytes. |
| static void SetNullIndicators(NullIndicatorOffset offset, int64_t num_tuples, |
| int64_t tuple_stride, uint8_t* tuple_mem); |
| |
| void* GetSlot(int offset) { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<char*>(this) + offset; |
| } |
| |
| const void* GetSlot(int offset) const { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<const char*>(this) + offset; |
| } |
| |
| bool* GetBoolSlot(int offset) { |
| return static_cast<bool*>(GetSlot(offset)); |
| } |
| |
| int32_t* GetIntSlot(int offset) { |
| return static_cast<int32_t*>(GetSlot(offset)); |
| } |
| |
| int64_t* GetBigIntSlot(int offset) { |
| return static_cast<int64_t*>(GetSlot(offset)); |
| } |
| |
| StringValue* GetStringSlot(int offset) { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<StringValue*>(reinterpret_cast<char*>(this) + offset); |
| } |
| |
| const StringValue* GetStringSlot(int offset) const { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<const StringValue*>( |
| reinterpret_cast<const char*>(this) + offset); |
| } |
| |
| CollectionValue* GetCollectionSlot(int offset) { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<CollectionValue*>(reinterpret_cast<char*>(this) + offset); |
| } |
| |
| const CollectionValue* GetCollectionSlot(int offset) const { |
| DCHECK(offset != -1); // -1 offset indicates non-materialized slot |
| return reinterpret_cast<const CollectionValue*>( |
| reinterpret_cast<const char*>(this) + offset); |
| } |
| |
| /// For C++/IR interop, we need to be able to look up types by name. |
| static const char* LLVM_CLASS_NAME; |
| |
| private: |
| DISALLOW_COPY_AND_ASSIGN(Tuple); |
| |
| /// Copy all referenced string and collection data by allocating memory from pool, |
| /// copying data, then updating pointers in tuple to reference copied data. |
| void DeepCopyVarlenData(const TupleDescriptor& desc, MemPool* pool); |
| |
| /// Copies all referenced string and collection data into 'data'. Increments 'data' and |
| /// 'offset' by the number of bytes written. Recursively writes collection tuple data |
| /// and referenced collection and string data. |
| void DeepCopyVarlenData(const TupleDescriptor& desc, char** data, int* offset, |
| bool convert_ptrs); |
| |
| /// Implementation of MaterializedExprs(). This function is replaced during |
| /// codegen. 'num_non_null_string_values' must be initialized by the caller. |
| template <bool COLLECT_STRING_VALS, bool NULL_POOL> |
| void IR_NO_INLINE MaterializeExprs(TupleRow* row, const TupleDescriptor& desc, |
| ScalarExprEvaluator* const* evals, MemPool* pool, |
| StringValue** non_null_string_values, int* total_string_lengths, |
| int* num_non_null_string_values); |
| |
| /// Helper for CopyStrings() to allocate 'bytes' of memory. Returns a pointer to the |
| /// allocated buffer on success. Otherwise an error was encountered, in which case NULL |
| /// is returned and 'status' is set to an error. This odd return convention is used to |
| /// avoid emitting unnecessary code for ~Status() in perf-critical code. |
| char* AllocateStrings(const char* err_ctx, RuntimeState* state, int64_t bytes, |
| MemPool* pool, Status* status) noexcept; |
| |
| }; |
| |
| } |
| |
| #endif |