//***************************************************************************************
// Off-chip shared memory allocation routines. 
//***************************************************************************************
//
// Author: Rob F. Van der Wijngaart
//         Intel Corporation
// Date:   12/22/2010
//
//***************************************************************************************
// 
// Copyright 2010 Intel Corporation
// 
//    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.
// 
#include <asm/RCCE_lib.h>

#ifdef CONFIG_ROCKCREEK

//......................................................................................
// GLOBAL VARIABLES USED BY THE LIBRARY
//......................................................................................
static RCCE_BLOCK_S RCCE_space;   // data structure used for tracking MPB memory blocks
static RCCE_BLOCK_S *RCCE_spacep; // pointer to RCCE_space
#ifdef _OPENMP
#pragma omp threadprivate (RCCE_space, RCCE_spacep)
#endif

// END GLOBAL VARIABLES USED BY THE LIBRARY
//......................................................................................

//--------------------------------------------------------------------------------------
// FUNCTION: RCCE_shmalloc_init
//--------------------------------------------------------------------------------------
// initialize memory allocator
//--------------------------------------------------------------------------------------
void RCCE_shmalloc_init(
  t_vcharp mem, // pointer to shared space that is to be managed by allocator
  size_t size   // size (bytes) of managed space
) {

  // create one block containing all memory for truly dynamic memory allocator
  RCCE_spacep = &RCCE_space;
  RCCE_spacep->tail = (RCCE_BLOCK *) kmalloc(sizeof(RCCE_BLOCK));
  RCCE_spacep->tail->free_size = size;
  RCCE_spacep->tail->space = mem;
  /* make a circular list by connecting tail to itself */
  RCCE_spacep->tail->next = RCCE_spacep->tail;
#ifdef SHMDBG 
kprintf("%s: %d: RCCE_spacep->tail->free_size, RCCE_spacep->tail->space: %x %x\n",
__FILE__, __LINE__,RCCE_spacep->tail->free_size, RCCE_spacep->tail->space);
#endif
}

//--------------------------------------------------------------------------------------
// FUNCTION: RCCE_shmalloc
//--------------------------------------------------------------------------------------
// Allocate memory in off-chip shared memory. This is a collective call that should be
// issued by all participating cores if consistent results are required. All cores will
// allocate space that is exactly overlapping. Alternatively, determine the beginning of
// the off-chip shared memory on all cores and subsequently let just one core do all the
// allocating and freeing. It can then pass offsets to other cores who need to know what
// shared memory regions were involved.
//--------------------------------------------------------------------------------------
t_vcharp RCCE_shmalloc(
  size_t size // requested space
) {

  t_vcharp result;

  // simple memory allocator, loosely based on public domain code developed by
  // Michael B. Allen and published on "The Scripts--IT /Developers Network".
  // Approach: 
  // - maintain linked list of pointers to memory. A block is either completely
  //   malloced (free_size = 0), or completely free (free_size > 0).
  //   The space field always points to the beginning of the block
  // - malloc: traverse linked list for first block that has enough space    
  // - free: Check if pointer exists. If yes, check if the new block should be 
  //         merged with neighbors. Could be one or two neighbors.

  RCCE_BLOCK *b1, *b2, *b3;   // running pointers for blocks              

  // Unlike the MPB, the off-chip shared memory is uncached by default, so can
  // be allocated in any increment, not just the cache line size
  if (size==0) return 0;

  // always first check if the tail block has enough space, because that
  // is the most likely. If it does and it is exactly enough, we still
  // create a new block that will be the new tail, whose free space is 
  // zero. This acts as a marker of where free space of predecessor ends   
//printf("RCCE_spacep->tail: %x\n",RCCE_spacep->tail);
  b1 = RCCE_spacep->tail;
  if (b1->free_size >= size) {
    // need to insert new block; new order is: b1->b2 (= new tail)         
    b2 = (RCCE_BLOCK *) kmalloc(sizeof(RCCE_BLOCK));
    b2->next      = b1->next;
    b1->next      = b2;
    b2->free_size = b1->free_size-size;
    b2->space     = b1->space + size;
    b1->free_size = 0;
    // need to update the tail                                             
    RCCE_spacep->tail = b2;
    return(b1->space);
  }

  // tail didn't have enough space; loop over whole list from beginning    
  while (b1->next->free_size < size) {
    if (b1->next == RCCE_spacep->tail) {
      return NULL; // we came full circle 
    }
    b1 = b1->next;
  }

  b2 = b1->next;
  if (b2->free_size > size) { // split block; new block order: b1->b2->b3  
    b3            = (RCCE_BLOCK *) kmalloc(sizeof(RCCE_BLOCK));
    b3->next      = b2->next; // reconnect pointers to add block b3        
    b2->next      = b3;       //     "         "     "  "    "    "        
    b3->free_size = b2->free_size - size; // b3 gets remainder free space  
    b3->space     = b2->space + size; // need to shift space pointer       
  } 
  b2->free_size = 0;          // block b2 is completely used               
  return (b2->space);
}

//--------------------------------------------------------------------------------------
// FUNCTION: RCCE_shfree
//--------------------------------------------------------------------------------------
// Deallocate memory in off-chip shared memory. Also collective, see RCCE_shmalloc
//--------------------------------------------------------------------------------------
void RCCE_shfree(
  t_vcharp ptr // pointer to data to be freed
  ) {

  RCCE_BLOCK *b1, *b2, *b3;   // running block pointers                    
  int j1, j2;                 // booleans determining merging of blocks    

  // loop over whole list from the beginning until we locate space ptr     
  b1 = RCCE_spacep->tail;
  while (b1->next->space != ptr && b1->next != RCCE_spacep->tail) { 
    b1 = b1->next;
  }

  // b2 is target block whose space must be freed    
  b2 = b1->next;              
  // tail either has zero free space, or hasn't been malloc'ed             
  if (b2 == RCCE_spacep->tail) return;      

  // reset free space for target block (entire block)                      
  b3 = b2->next;
  b2->free_size = b3->space - b2->space;

  // determine with what non-empty blocks the target block can be merged   
  j1 = (b1->free_size>0 && b1!=RCCE_spacep->tail); // predecessor block    
  j2 = (b3->free_size>0 || b3==RCCE_spacep->tail); // successor block      

  if (j1) {
    if (j2) { // splice all three blocks together: (b1,b2,b3) into b1      
      b1->next = b3->next;
      b1->free_size +=  b3->free_size + b2->free_size;
      if (b3==RCCE_spacep->tail) RCCE_spacep->tail = b1;
      kfree(b3, sizeof(RCCE_BLOCK));
    } 
    else {    // only merge (b1,b2) into b1                                
      b1->free_size += b2->free_size;
      b1->next = b3;
    }
    kfree(b2, sizeof(RCCE_BLOCK));
  } 
  else {
    if (j2) { // only merge (b2,b3) into b2                                
      b2->next = b3->next;
      b2->free_size += b3->free_size;
      if (b3==RCCE_spacep->tail) RCCE_spacep->tail = b2;
      kfree(b3, sizeof(RCCE_BLOCK));
    } 
  }
}


//--------------------------------------------------------------------------------------
// FUNCTION: RCCE_shflush
//--------------------------------------------------------------------------------------
// this function makes sure that data in shared memory can be read or written
//--------------------------------------------------------------------------------------
void RCCE_shflush() {
#ifdef _OPENMP
#pragma omp flush
#else

#endif
}  

#endif