| /* cilk-abi-vla.cpp -*-C++-*- |
| * |
| ************************************************************************* |
| * |
| * @copyright |
| * Copyright (C) 2013, Intel Corporation |
| * All rights reserved. |
| * |
| * @copyright |
| * 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 Intel Corporation nor the names of its |
| * contributors may be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * |
| * @copyright |
| * 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 |
| * HOLDER 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. |
| * |
| **************************************************************************/ |
| |
| /* |
| * Implementation of Variable Length Array (VLA) ABI. |
| * |
| * __cilkrts_stack_alloc() and __cilkrts_stack_free must be compiled |
| * such that ebp/rbp is used for the stack frames. This is done by having |
| * each of them use alloca, which forces the special frame types needed on |
| * each of the ABIs. Additionally, for some forms of stack frame, special |
| * care must be taken because the alloca space may not be at the bottom of the |
| * stack frame of the caller. For Intel64 windows, and for some options |
| * with other ABIs, a preallocated parameter block may exist on the stack |
| * at a lower address than the alloca. If this is the case, the parameter |
| * distance_from_sp_to_alloca_area will be non-zero, and will indicate how |
| * much pre-allocated parameter space resides in the caller's stack frame |
| * between the alloca area, and the bottom of the stack when the call to |
| * the cilkrts is made. As such, when non-zero it also includes any space |
| * used for passing the cilkrts_stack_alloc or cilkrts_stack_free parameters. |
| */ |
| |
| #include <assert.h> |
| #include <stdlib.h> |
| #include <stdint.h> |
| |
| // Getting a definition for alloca appears to be a pain in the butt. Here's |
| // a variant on what's recommended in the autoconf doc |
| #if defined _MSC_VER |
| # include <malloc.h> |
| # define alloca _alloca |
| #elif defined HAVE_ALLOCA_H |
| # include <alloca.h> |
| #elif defined __GNUC__ |
| # define alloca __builtin_alloca |
| #elif defined _AIX |
| # define alloca __alloca |
| #else |
| # include <stddef.h> |
| # ifdef __cplusplus |
| extern "C" |
| # endif |
| void *alloca (size_t); |
| #endif |
| |
| #ifdef _WIN32 |
| # define INLINE static __inline |
| # pragma warning(disable:1025) // Don't whine about zero extending result of unary operation |
| #else |
| # define INLINE static inline |
| #endif |
| |
| |
| #include "internal/abi.h" |
| #include "cilk-abi-vla-internal.h" |
| |
| #if defined(__x86_64) || defined(_M_X64) |
| INLINE void setsp(void *val) |
| { |
| __asm__("movq %0, %%rsp" : : "r"(val): "rsp"); |
| } |
| INLINE char* getsp(void) |
| { |
| void *res; |
| |
| __asm__("movq %%rsp, %0" : "=r"(res): : "rsp"); |
| return res; |
| } |
| INLINE char* getbp(void) |
| { |
| void *res; |
| |
| __asm__("movq %%rbp, %0" : "=r"(res): : "rbp"); |
| return res; |
| } |
| INLINE void copy_frame_down_and_move_bp( |
| char *dst, |
| char *src, |
| size_t cpy_bytes, |
| char *new_ebp |
| ) |
| { |
| // In this version, dst is guaranteed to be lower address than src, |
| // therefore copying upwards from src into dst is safe in case |
| // there is overlap. The number of bytes is also guaranteed to be |
| // a multiple of 8, and the copy is done in 64 bit word chunks for |
| // best efficiency. |
| __asm__( |
| "movq %0, %%rdi;" |
| "movq %1, %%rsi;" |
| "movq %2, %%rcx;" |
| "shrq $3, %%rcx;" |
| "rep movsq;" |
| "movq %3, %%rbp" : |
| : |
| "rm"(dst), "rm"(src), "rm"(cpy_bytes), "rm"(new_ebp) : |
| "rsi", "rdi", "rcx", "rbp", "memory"); |
| } |
| INLINE void copy_frame_up_and_move_bp( |
| char *dst, |
| char *src, |
| size_t cpy_bytes, |
| char *new_ebp |
| ) |
| { |
| // In this version, dst is guaranteed to be higher address than src, |
| // therefore copying downwards from src into dst is safe in case |
| // there is overlap. The number of bytes is also guaranteed to be |
| // a multiple of 8, and the copy is done in 64 bit word chunks for |
| // best efficiency. |
| dst += cpy_bytes - 8; |
| src += cpy_bytes - 8; |
| __asm__( |
| "movq %0, %%rdi;" |
| "movq %1, %%rsi;" |
| "movq %2, %%rcx;" |
| "shrq $3, %%rcx;" |
| "std; rep movsq; cld;" |
| "movl %3, %%rbp;" : |
| : |
| "rm"(dst), "rm"(src), "rm"(cpy_bytes), "rm"(new_ebp) : |
| "rsi", "rdi", "rcx", "rbp", "memory"); |
| } |
| #else |
| INLINE void setsp(void *val) |
| { |
| __asm__("movl %0, %%esp" : : "r"(val): "esp"); |
| } |
| INLINE char* getsp(void) |
| { |
| void *res; |
| |
| __asm__("movl %%esp, %0" : "=r"(res): : "esp"); |
| return res; |
| } |
| INLINE char* getbp(void) |
| { |
| void *res; |
| |
| __asm__("movl %%ebp, %0" : "=r"(res): : "ebp"); |
| return res; |
| } |
| INLINE void copy_frame_down_and_move_bp( |
| char *dst, |
| char *src, |
| size_t cpy_bytes, |
| char *new_ebp |
| ) |
| { |
| // In this version, dst is guaranteed to be lower address than src, |
| // therefore copying upwards from src into dst is safe in case |
| // there is overlap. The number of bytes is also guaranteed to be |
| // a multiple of 4, and the copy is done in 32 bit word chunks for |
| // best efficiency. |
| __asm__( |
| "movl %0, %%edi;" |
| "movl %1, %%esi;" |
| "movl %2, %%ecx;" |
| "shrl $2, %%ecx;" |
| "rep movsd;" |
| "movl %3, %%ebp" : |
| : |
| "rm"(dst), "rm"(src), "rm"(cpy_bytes), "rm"(new_ebp) : |
| "esi", "edi", "ecx", "ebp", "memory"); |
| } |
| INLINE void copy_frame_up_and_move_bp( |
| char *dst, |
| char *src, |
| size_t cpy_bytes, |
| char *new_ebp |
| ) |
| { |
| // In this version, dst is guaranteed to be higher address than src, |
| // therefore copying downwards from src into dst is safe in case |
| // there is overlap. The number of bytes is also guaranteed to be |
| // a multiple of 4, and the copy is done in 32 bit word chunks for |
| // best efficiency. |
| dst += cpy_bytes - 4; |
| src += cpy_bytes - 4; |
| __asm__( |
| "movl %0, %%edi;" |
| "movl %1, %%esi;" |
| "movl %2, %%ecx;" |
| "shrl $2, %%ecx;" |
| "std; rep movsd; cld;" |
| "movl %3, %%ebp" : |
| // "=D"(dst), "=S"(src), "=C"(cpy_bytes) : |
| : |
| "rm"(dst), "rm"(src), "rm"(cpy_bytes), "rm"(new_ebp) : |
| "esi", "edi", "ecx", "ebp", "memory"); |
| } |
| #endif |
| |
| |
| #define c_cilk_ptr_from_heap 0xc2f2f00d |
| #define c_cilk_ptr_from_stack 0xc3f30d0f |
| |
| CILK_ABI(__cilkrts_void_ptr) |
| __cilkrts_stack_alloc( |
| __cilkrts_stack_frame *sf, |
| size_t size, |
| size_t distance_from_sp_to_alloca_area, |
| uint32_t align, // align is always >= minimum stack alignment and |
| // >= ptr_size as well, and must be a power of 2. |
| uint32_t needs_tag // non-zero if the pointer being returned needs to |
| // be tagged |
| ) |
| { |
| #ifdef __INTEL_COMPILER |
| // full_size will be a multiple of align, and contains |
| // enough extra space to allocate a marker. |
| size_t full_size = (size + align - 1) & ~(align - 1); |
| |
| if (needs_tag) { |
| full_size += align; |
| } |
| |
| char *t; |
| if (sf->worker != 0 && |
| ((sf->flags & CILK_FRAME_UNSYNCHED) != 0)) { |
| t = vla_internal_heap_alloc(sf, full_size, align); |
| if (needs_tag) { |
| t += align; |
| ((uint32_t*)t)[-1] = c_cilk_ptr_from_heap; |
| } |
| return (void *)t; |
| } |
| |
| // stack is still synced, allocate full_size from esp, |
| // and record in 32 bits immediately below the space |
| // allocated that this was space that this was |
| // allocated in the stack. |
| char *old_ebp = getbp(); |
| char *old_esp = getsp(); |
| |
| // make top_ptr point to base of first parameter. |
| char *top_ptr = ((char *)(_AddressOfReturnAddress()) + |
| sizeof(char *)); |
| size_t param_size = 0; |
| |
| #if defined(__x86_64) |
| // For Intel64 linux & MACH ABI, all the parameters were passed in |
| // register, so top of the stack frame above the return address |
| // is just the size of the return address plus |
| // distance_from_sp_to_alloca_area on the chance that the alloca |
| // area isn't at the very bottom of the calling functions stack. |
| #elif defined(__MACH__) |
| // For ia32 MACH, parameter size is always a mutliple of 16 |
| // bytes to keep the stack 16 byte aligned. So we need to round |
| // number of parameters up to multiple of 4. |
| param_size = 8 * sizeof(char *); |
| #else |
| // For both windows Intel64 ABI, and the IA32 windows and |
| // linux ABIs, space is reserved on the stack for all these |
| // parameters. param_size is 5 * size of a stack slot. |
| param_size = 5 * sizeof(char *); |
| #endif |
| |
| // now make top_ptr point above the params, or if |
| // distance_from_sp_to_alloca_area is not zero, make |
| // it point above that area. When non-zero, |
| // distance_from_sp_to_alloca area is expected to contain |
| // the parameter space, so we only add one or the other, |
| // not both. |
| top_ptr += (distance_from_sp_to_alloca_area != 0) ? |
| distance_from_sp_to_alloca_area : param_size; |
| |
| // t needs to end up at current value of top_ptr less full_size and less |
| // distance_from_sp_to_alloca_area and |
| // then rounded down to the alignment needed. Then we have to bump |
| // esp down by current frame_size, so that when all is done with respect |
| // to executing the return sequence, the final value of esp will be the |
| // same value as t. |
| t = (top_ptr - full_size) - distance_from_sp_to_alloca_area; |
| intptr_t temp = (intptr_t)t; |
| temp &= ~((intptr_t)(align - 1)); |
| t = (char *)temp; |
| |
| // ok, the value of t is set where we need it. Now set esp |
| // to the value of t less the current frame size. |
| // So now when we do regular return esp should be left such |
| // that it has moved down by full_size. |
| size_t cur_fm_size = (top_ptr - old_esp); |
| char *new_esp = t - cur_fm_size; |
| char *new_ebp = old_ebp - (old_esp - new_esp); |
| |
| // extend the stack down by at least the difference between where |
| // I want it to be and where it currently is. This should take care |
| // of touching any pages necessary. |
| char *foo = alloca(old_esp - new_esp); |
| setsp(foo < new_esp ? foo : new_esp); |
| |
| // Now set esp exactly where I want it. |
| // setsp(new_esp); |
| |
| copy_frame_down_and_move_bp(new_esp, old_esp, cur_fm_size, new_ebp); |
| |
| if (needs_tag) { |
| t += align; |
| ((uint32_t*)t)[-1] = c_cilk_ptr_from_stack; |
| } |
| |
| return t; |
| #else // Not __INTEL_COMPILER |
| // Not supported unless we can figure out how to get the size of the frame |
| return NULL; |
| #endif |
| } |
| |
| // This frees the space allocated for a variable length array. |
| CILK_ABI(void) |
| __cilkrts_stack_free( |
| __cilkrts_stack_frame *sf, |
| void *p, |
| size_t size, |
| size_t distance_from_sp_to_alloca_area, |
| uint32_t align, // same requirements as for align in allocation, |
| // and must match alignment that was passed when |
| // doing the allocation |
| uint32_t known_from_stack // non-zero if this is known to be allocated |
| // on the stack, and therefore has no tag |
| ) |
| { |
| #ifdef __INTEL_COMPILER |
| uint32_t *t = (uint32_t*)p; |
| |
| // full_size will be a multiple of align, and contains |
| // enough extra space to allocate a marker if one was needed. |
| size_t full_size = (size + align - 1) & ~(align - 1); |
| if (known_from_stack == 0) { |
| // if the compiler hasn't told the run-time that this is |
| // known to be on the stack, then this pointer must have been |
| // tagged such that the run-time can tell. |
| assert(t[-1] == c_cilk_ptr_from_stack || |
| t[-1] == c_cilk_ptr_from_heap); |
| |
| known_from_stack = t[-1] == c_cilk_ptr_from_stack; |
| full_size += align; // accounts for extra space for marker |
| t = (uint32_t *)(((char *)t) - align); |
| } |
| |
| if (known_from_stack) { |
| // alloca useage forces an ebp/rbp based stack frame even though |
| // 0 and unused. |
| char *foo = alloca(0); |
| if (sf->worker == 0 || (sf->flags & CILK_FRAME_UNSYNCHED) == 0) { |
| // p was allocated from current stack frame and we |
| // are synced on current stack frame. Return the |
| // amount of the stack that needs to be freed. |
| char *old_ebp = getbp(); |
| char *old_esp = getsp(); |
| |
| // make top_ptr point to base of first parameter. |
| char *top_ptr = ((char *)(_AddressOfReturnAddress()) + |
| sizeof(char *)); |
| size_t param_size = 0; |
| |
| #if defined(__x86_64) |
| // For Intel64 linux & MACH ABI, all the parameters were passed in |
| // register, so top of the stack frame above the return address |
| // is just the size of the return address plus |
| // distance_from_sp_to_alloca_area on the chance that the alloca |
| // area isn't at the very bottom of the calling functions stack. |
| #elif defined(__MACH__) |
| // For ia32 MACH, parameter size is always a mutliple of 16 |
| // bytes to keep the stack 16 byte aligned. So we need to round |
| // number of parameters up to multiple of 4. |
| param_size = 8 * sizeof(char *); |
| #else |
| // For both windows Intel64 ABI, and the IA32 windows and |
| // linux ABIs, space is reserved on the stack for all these |
| // parameters. param_size is 5 * size of a stack slot. |
| param_size = 6 * sizeof(char *); |
| #endif |
| |
| // now make top_ptr point above the params, or if |
| // distance_from_sp_to_alloca_area is not zero, make |
| // it point above that area. When non-zero, |
| // distance_from_sp_to_alloca area is expected to contain |
| // the parameter space, so we only add one or the other, |
| // not both. |
| top_ptr += (distance_from_sp_to_alloca_area != 0) ? |
| distance_from_sp_to_alloca_area : param_size; |
| |
| size_t cur_fm_size = (top_ptr - old_esp); |
| char *new_esp = old_esp + full_size; |
| char *new_ebp = old_ebp + full_size; |
| |
| copy_frame_up_and_move_bp(new_esp, old_esp, cur_fm_size, new_ebp); |
| setsp(new_esp); |
| } |
| else { |
| // p was allocated on stack frame, but that is |
| // no longer the current stack frame. Need to adjust the |
| // saved esp that is somewhere in the cilk runtime so that |
| // on sync, esp will be cut back correctly. |
| vla_free_from_original_stack(sf, full_size); |
| } |
| } |
| else { |
| vla_internal_heap_free(t, full_size); |
| } |
| #else // Not __INTEL_COMPILER |
| // Not supported unless we can figure out how to get the size of the frame |
| #endif |
| } |
