LRU_List.c

Go to the documentation of this file.

/*
 * vim:expandtab:shiftwidth=8:tabstop=8:
 *
 * Copyright CEA/DAM/DIF  (2008)
 * contributeur : Philippe DENIEL   philippe.deniel@cea.fr
 *                Thomas LEIBOVICI  thomas.leibovici@cea.fr
 *
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 3 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * ---------------------------------------
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "LRU_List.h"
#include "abstract_mem.h"
#include "log.h"

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif


/* ------ This group contains all the functions used to manipulate the LRU from outside this module ----- */

LRU_list_t *LRU_Init(LRU_parameter_t lru_param, LRU_status_t * pstatus)
{
  LRU_list_t *plru = NULL;
  char *name __attribute__((unused)) = "Unamed";

  if (lru_param.lp_name != NULL)
    name = lru_param.lp_name;

  /* Sanity check */
  if((plru = gsh_malloc(sizeof(LRU_list_t))) == NULL)
    {
      *pstatus = LRU_LIST_MALLOC_ERROR;
      return NULL;
    }

  plru->nb_entry = 0;
  plru->nb_invalid = 0;
  plru->nb_call_gc = 0;
  plru->MRU = plru->LRU = NULL;
  plru->parameter = lru_param;

  /* Pre allocate entries */
  plru->lru_entry_pool = pool_init("LRU Entry Pool",
                                   sizeof(LRU_entry_t),
                                   pool_basic_substrate,
                                   NULL, NULL, NULL);
  if(!(plru->lru_entry_pool))
    {
      *pstatus = LRU_LIST_MALLOC_ERROR;
      return NULL;
    }

  *pstatus = LRU_LIST_SUCCESS;
  return plru;
}                               /* LRU_Init */

int LRU_invalidate(LRU_list_t * plru, LRU_entry_t * pentry)
{
  if(pentry->valid_state != LRU_ENTRY_INVALID)
    {
      pentry->valid_state = LRU_ENTRY_INVALID;
      plru->nb_invalid += 1;
    }

  return LRU_LIST_SUCCESS;
}                               /* LRU_invalidate */

LRU_entry_t *LRU_new_entry(LRU_list_t * plru, LRU_status_t * pstatus)
{
  LRU_entry_t *new_entry = NULL;

  LogDebug(COMPONENT_LRU,
           "==> LRU_new_entry: nb_entry = %d nb_entry_prealloc = %d",
           plru->nb_entry, plru->parameter.nb_entry_prealloc);

  new_entry = pool_alloc(plru->lru_entry_pool, NULL);
  if(new_entry == NULL)
    {
      *pstatus = LRU_LIST_MALLOC_ERROR;
      return NULL;
    }

  new_entry->valid_state = LRU_ENTRY_VALID;
  new_entry->next = NULL;       /* Entry is added as the MRU entry */

  if(plru->MRU == NULL)
    {
      new_entry->prev = NULL;
      plru->LRU = new_entry;
    }
  else
    {
      new_entry->prev = plru->MRU;
      plru->MRU->next = new_entry;
    }

  plru->nb_entry += 1;
  plru->nb_call_gc += 1;
  plru->MRU = new_entry;

  *pstatus = LRU_LIST_SUCCESS;
  return new_entry;
}                               /* LRU_new_entry */


static inline void _LRU_remove_entry(LRU_list_t * plru, LRU_entry_t * const pentry)
{
    if(pentry->prev != NULL)
        pentry->prev->next = pentry->next;
    else {
        assert(pentry == plru->LRU); // we remove the list head
        plru->LRU = pentry->next;
    }

    if(pentry->next != NULL)
        pentry->next->prev = pentry->prev;
    else {
        assert(pentry == plru->MRU);    // we remove the MRU
        plru->MRU = NULL;
    }
    plru->nb_entry --;
    /* Put it back to pre-allocated pool */
    pool_free(plru->lru_entry_pool, pentry);
}

int LRU_pop_entry (LRU_list_t * plru, LRU_entry_t  *out_entry)
{
    LRU_entry_t * const pentry = plru->LRU;
    void  *pdata __attribute__((unused));

    if (plru->nb_entry == 0) {
        return LRU_LIST_EMPTY_LIST;
    }
    memcpy(out_entry, pentry, sizeof(*out_entry));
    pdata = pentry->buffdata.pdata;
    _LRU_remove_entry(plru, pentry);
    return LRU_LIST_SUCCESS;
}

int LRU_gc_invalid(LRU_list_t * plru, void *cleanparam)
{
  LRU_entry_t *pentry = NULL;
  LRU_entry_t *pentrynext = NULL;
  int rc = 0;

  if(plru == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->nb_invalid == 0)
    return LRU_LIST_SUCCESS;    /* Nothing to be done in this case */

  if(plru->MRU == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->MRU->prev == NULL)   /* One entry only, returns success (the MRU cannot be invalid) */
    return LRU_LIST_SUCCESS;

  /* Do nothing if not enough calls were done */
  if(plru->nb_call_gc < plru->parameter.nb_call_gc_invalid)
    return LRU_LIST_SUCCESS;
  plru->nb_call_gc = 0;

  /* From the LRU to the entry BEFORE the MRU */
  rc = LRU_LIST_SUCCESS;

  for(pentry = plru->LRU; pentry != plru->MRU; pentry = pentrynext)
    {
      pentrynext = pentry->next;

      if(pentry->valid_state == LRU_ENTRY_INVALID)
        {
          if(plru->parameter.clean_entry(pentry, cleanparam) != 0)
            {
              LogDebug(COMPONENT_LRU, "Error cleaning pentry %p", pentry);
              rc = LRU_LIST_BAD_RELEASE_ENTRY;
            }

          _LRU_remove_entry(plru, pentry);
          plru->nb_invalid --;
        }
    }

  return rc;
}                               /* LRU_gc_invalid */

int LRU_invalidate_by_function(LRU_list_t * plru,
                               int (*testfunc) (LRU_entry_t *, void *addparam),
                               void *addparam)
{
  LRU_entry_t *pentry = NULL;
  LRU_entry_t *pentry_next = NULL;
  int rc = 0;

  if(plru == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->nb_entry == 0)
    return LRU_LIST_SUCCESS;    /* Nothing to be done in this case */

  if(plru->MRU == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->MRU->prev == NULL)   /* One entry only, returns success (the MRU cannot be set invalid) */
    return LRU_LIST_SUCCESS;

  /* From the LRU to the entry BEFORE the MRU */
  rc = LRU_LIST_SUCCESS;

  for(pentry = plru->LRU; pentry != plru->MRU; pentry = pentry_next)
    {
      pentry_next = pentry->next;
      if(pentry->valid_state != LRU_ENTRY_INVALID)
        {
          /* Use test function on the entry to know if it should be set invalid or not */
          if(testfunc(pentry, addparam) == LRU_LIST_SET_INVALID)
            {
              if((rc = LRU_invalidate(plru, pentry)) != LRU_LIST_SUCCESS)
                break;          /* end of loop, error will be returned */
            }
        }
    }

  return rc;
}                               /* LRU_invalidate_by_function */

int LRU_apply_function(LRU_list_t * plru, int (*myfunc) (LRU_entry_t *, void *addparam),
                       void *addparam)
{
  LRU_entry_t *pentry = NULL;
  int rc = 0;

  if(plru == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->nb_entry == 0)
    return LRU_LIST_SUCCESS;    /* Nothing to be done in this case */

  if(plru->MRU == NULL)
    return LRU_LIST_EMPTY_LIST;

  if(plru->MRU->prev == NULL)   /* One entry only, returns success (the MRU cannot be set invalid) */
    return LRU_LIST_SUCCESS;

  /* From the LRU to the entry BEFORE the MRU */
  rc = LRU_LIST_SUCCESS;
  for(pentry = plru->MRU->prev; pentry != NULL; pentry = pentry->prev)
    {
      if(pentry->valid_state != LRU_ENTRY_INVALID)
        {
          /* Use test function on the entry to know if it should be set invalid or not */
          if(myfunc(pentry, addparam) == FALSE)
            {
              break;            /* end of loop */
            }
        }
    }                           /* for */

  return rc;

}                               /* LRU_apply_function */

void LRU_Print(LRU_list_t * plru)
{
  LRU_entry_t *pentry = NULL;
  char dispdata[LRU_DISPLAY_STRLEN];

  for(pentry = plru->LRU; pentry != NULL; pentry = pentry->next)
    {
      plru->parameter.entry_to_str(pentry->buffdata, dispdata);
      LogFullDebug(COMPONENT_LRU,
                   "Entry value = %s, valid_state = %d",
                   dispdata, pentry->valid_state);
    }
  LogFullDebug(COMPONENT_LRU, "-----------------------------------------");
}                               /* LRU_Print */

/* @} */