|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
310c69 |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
310c69 |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
310c69 |
* of the License, or (at your option) any later version.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
310c69 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
310c69 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
310c69 |
* GNU General Public License for more details.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
310c69 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
310c69 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
310c69 |
* 02110-1301, USA.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/dirtyLists.c#1 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "dirtyLists.h"
|
|
Packit Service |
310c69 |
#include "dirtyListsInternals.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "logger.h"
|
|
Packit Service |
310c69 |
#include "memoryAlloc.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "types.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
struct dirtyLists {
|
|
Packit Service |
310c69 |
/** The number of periods after which an element will be expired */
|
|
Packit Service |
310c69 |
BlockCount maximumAge;
|
|
Packit Service |
310c69 |
/** The oldest period which has unexpired elements */
|
|
Packit Service |
310c69 |
SequenceNumber oldestPeriod;
|
|
Packit Service |
310c69 |
/** One more than the current period */
|
|
Packit Service |
310c69 |
SequenceNumber nextPeriod;
|
|
Packit Service |
310c69 |
/** The function to call on expired elements */
|
|
Packit Service |
310c69 |
DirtyCallback *callback;
|
|
Packit Service |
310c69 |
/** The callback context */
|
|
Packit Service |
310c69 |
void *context;
|
|
Packit Service |
310c69 |
/** The offset in the array of lists of the oldest period */
|
|
Packit Service |
310c69 |
BlockCount offset;
|
|
Packit Service |
310c69 |
/** The list of elements which are being expired */
|
|
Packit Service |
310c69 |
RingNode expired;
|
|
Packit Service |
310c69 |
/** The lists of dirty elements */
|
|
Packit Service |
310c69 |
RingNode lists[];
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
int makeDirtyLists(BlockCount maximumAge,
|
|
Packit Service |
310c69 |
DirtyCallback *callback,
|
|
Packit Service |
310c69 |
void *context,
|
|
Packit Service |
310c69 |
DirtyLists **dirtyListsPtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
DirtyLists *dirtyLists;
|
|
Packit Service |
310c69 |
int result = ALLOCATE_EXTENDED(DirtyLists, maximumAge, RingNode, __func__,
|
|
Packit Service |
310c69 |
&dirtyLists);
|
|
Packit Service |
310c69 |
if (result != VDO_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
dirtyLists->maximumAge = maximumAge;
|
|
Packit Service |
310c69 |
dirtyLists->callback = callback;
|
|
Packit Service |
310c69 |
dirtyLists->context = context;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
initializeRing(&dirtyLists->expired);
|
|
Packit Service |
310c69 |
for (BlockCount i = 0; i < maximumAge; i++) {
|
|
Packit Service |
310c69 |
initializeRing(&dirtyLists->lists[i]);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
*dirtyListsPtr = dirtyLists;
|
|
Packit Service |
310c69 |
return VDO_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void freeDirtyLists(DirtyLists **dirtyListsPtr)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
DirtyLists *lists = *dirtyListsPtr;
|
|
Packit Service |
310c69 |
if (lists == NULL) {
|
|
Packit Service |
310c69 |
return;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
FREE(lists);
|
|
Packit Service |
310c69 |
*dirtyListsPtr = NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void setCurrentPeriod(DirtyLists *dirtyLists, SequenceNumber period)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
ASSERT_LOG_ONLY(dirtyLists->nextPeriod == 0, "current period not set");
|
|
Packit Service |
310c69 |
dirtyLists->oldestPeriod = period;
|
|
Packit Service |
310c69 |
dirtyLists->nextPeriod = period + 1;
|
|
Packit Service |
310c69 |
dirtyLists->offset = period % dirtyLists->maximumAge;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Expire the oldest list.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param dirtyLists The DirtyLists to expire
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void expireOldestList(DirtyLists *dirtyLists)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
dirtyLists->oldestPeriod++;
|
|
Packit Service |
310c69 |
RingNode *ring = &(dirtyLists->lists[dirtyLists->offset++]);
|
|
Packit Service |
310c69 |
if (!isRingEmpty(ring)) {
|
|
Packit Service |
310c69 |
spliceRingChainBefore(ring->next, ring->prev, &dirtyLists->expired);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (dirtyLists->offset == dirtyLists->maximumAge) {
|
|
Packit Service |
310c69 |
dirtyLists->offset = 0;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Update the period if necessary.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param dirtyLists The DirtyLists
|
|
Packit Service |
310c69 |
* @param period The new period
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void updatePeriod(DirtyLists *dirtyLists, SequenceNumber period)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
while (dirtyLists->nextPeriod <= period) {
|
|
Packit Service |
310c69 |
if ((dirtyLists->nextPeriod - dirtyLists->oldestPeriod)
|
|
Packit Service |
310c69 |
== dirtyLists->maximumAge) {
|
|
Packit Service |
310c69 |
expireOldestList(dirtyLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
dirtyLists->nextPeriod++;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Write out the expired list.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param dirtyLists The dirtyLists
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void writeExpiredElements(DirtyLists *dirtyLists)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (isRingEmpty(&dirtyLists->expired)) {
|
|
Packit Service |
310c69 |
return;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
dirtyLists->callback(&dirtyLists->expired, dirtyLists->context);
|
|
Packit Service |
310c69 |
ASSERT_LOG_ONLY(isRingEmpty(&dirtyLists->expired),
|
|
Packit Service |
310c69 |
"no expired elements remain");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void addToDirtyLists(DirtyLists *dirtyLists,
|
|
Packit Service |
310c69 |
RingNode *node,
|
|
Packit Service |
310c69 |
SequenceNumber oldPeriod,
|
|
Packit Service |
310c69 |
SequenceNumber newPeriod)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if ((oldPeriod == newPeriod)
|
|
Packit Service |
310c69 |
|| ((oldPeriod != 0) && (oldPeriod < newPeriod))) {
|
|
Packit Service |
310c69 |
return;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (newPeriod < dirtyLists->oldestPeriod) {
|
|
Packit Service |
310c69 |
pushRingNode(&dirtyLists->expired, node);
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
updatePeriod(dirtyLists, newPeriod);
|
|
Packit Service |
310c69 |
pushRingNode(&dirtyLists->lists[newPeriod % dirtyLists->maximumAge], node);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
writeExpiredElements(dirtyLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void advancePeriod(DirtyLists *dirtyLists, SequenceNumber period)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
updatePeriod(dirtyLists, period);
|
|
Packit Service |
310c69 |
writeExpiredElements(dirtyLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
void flushDirtyLists(DirtyLists *dirtyLists)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
while (dirtyLists->oldestPeriod < dirtyLists->nextPeriod) {
|
|
Packit Service |
310c69 |
expireOldestList(dirtyLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
writeExpiredElements(dirtyLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
SequenceNumber getDirtyListsNextPeriod(DirtyLists *dirtyLists)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return dirtyLists->nextPeriod;
|
|
Packit Service |
310c69 |
}
|