diff --git a/src/backend/access/transam/generic_xlog.c b/src/backend/access/transam/generic_xlog.c index 3adbf7b..2ed4146 100644 --- a/src/backend/access/transam/generic_xlog.c +++ b/src/backend/access/transam/generic_xlog.c @@ -44,8 +44,16 @@ *------------------------------------------------------------------------- */ #define FRAGMENT_HEADER_SIZE (2 * sizeof(OffsetNumber)) +#define DIFF_DELTA_HEADER_SIZE (sizeof(char) + sizeof(int)) #define MATCH_THRESHOLD FRAGMENT_HEADER_SIZE -#define MAX_DELTA_SIZE (BLCKSZ + 2 * FRAGMENT_HEADER_SIZE) +#define MAX_DELTA_SIZE (BLCKSZ + 2 * FRAGMENT_HEADER_SIZE + \ + 2 * DIFF_DELTA_HEADER_SIZE) + sizeof(bool) + +#define MAX_ALIGN_MISMATCHES 24 +/* MAX_ALIGN_MISMATCHES is supposed to be not greater than PG_UINT8_MAX */ + +#define writeToPtr(ptr, x) memcpy(ptr, &(x), sizeof(x)), ptr += sizeof(x) +#define readFromPtr(ptr, x) memcpy(&(x), ptr, sizeof(x)), ptr += sizeof(x) /* Struct of generic xlog data for single page */ typedef struct @@ -71,15 +79,62 @@ struct GenericXLogState bool isLogged; }; +/* Describes for the region which type of delta is used in it */ +typedef enum +{ + DIFF_DELTA = 0, /* diff delta with insert, remove and replace + * operations */ + BASE_DELTA = 1 /* base delta with update operations only */ +} DeltaType; + +/* Diff delta operations for transforming current page to target page */ +typedef enum +{ + DIFF_INSERT = 0, + DIFF_REMOVE = 1, + DIFF_REPLACE = 2 +} DiffDeltaOperations; + static void writeFragment(PageData *pageData, OffsetNumber offset, OffsetNumber len, const char *data); static void computeRegionDelta(PageData *pageData, const char *curpage, const char *targetpage, int targetStart, int targetEnd, - int validStart, int validEnd); + int validStart, int validEnd, + bool forceBaseDelta); static void computeDelta(PageData *pageData, Page curpage, Page targetpage); static void applyPageRedo(Page page, const char *delta, Size deltaSize); +static int alignRegions(const char *curRegion, const char *targetRegion, + int curRegionLen, int targetRegionLen); + +static bool computeRegionDiffDelta(PageData *pageData, + const char *curpage, const char *targetpage, + int targetStart, int targetEnd, + int validStart, int validEnd); +static const char *applyPageDiffRedo(Page page, const char *delta, Size deltaSize); + +static void computeRegionBaseDelta(PageData *pageData, + const char *curpage, const char *targetpage, + int targetStart, int targetEnd, + int validStart, int validEnd); +static const char *applyPageBaseRedo(Page page, const char *delta, Size deltaSize); + +static bool pageDataContainsDiffDelta(PageData *pageData); +static void downgradeDeltaToBaseFormat(PageData *pageData); + +/* Arrays for the alignment building and for the resulting alignments */ +static int V[MAX_ALIGN_MISMATCHES + 1][2 * MAX_ALIGN_MISMATCHES + 1]; +static int prevDiag[MAX_ALIGN_MISMATCHES + 1][2 * MAX_ALIGN_MISMATCHES + 1]; +static int alignmentDiag[MAX_ALIGN_MISMATCHES + 1]; +static char curRegionAligned[BLCKSZ + MAX_ALIGN_MISMATCHES]; +static bool curRegionAlignedGap[BLCKSZ + MAX_ALIGN_MISMATCHES]; +static char targetRegionAligned[BLCKSZ + MAX_ALIGN_MISMATCHES]; +static bool targetRegionAlignedGap[BLCKSZ + MAX_ALIGN_MISMATCHES]; + +/* Array for diff delta application */ +static char localPage[BLCKSZ]; + /* * Write next fragment into pageData's delta. @@ -115,14 +170,76 @@ writeFragment(PageData *pageData, OffsetNumber offset, OffsetNumber length, * Bytes in curpage outside the range validStart to validEnd-1 should be * considered invalid, and always overwritten with target data. * - * This function is a hot spot, so it's worth being as tense as possible - * about the data-matching loops. + * If forceBaseDelta is true, fucntion just calls computeRegionBaseDelta. + * Otherwise this function tries to build diff delta first and, if it fails, + * uses the base delta. It also provides the header before the delta in which + * the type and the length of the delta are contained. */ static void computeRegionDelta(PageData *pageData, const char *curpage, const char *targetpage, int targetStart, int targetEnd, - int validStart, int validEnd) + int validStart, int validEnd, + bool forceBaseDelta) +{ + int length; + char header; + int prevDeltaLen; + bool diff = false; + char *ptr = pageData->delta + pageData->deltaLen; + + /* Verify we have enough space */ + Assert(pageData->deltaLen + sizeof(header) + + sizeof(length) <= MAX_DELTA_SIZE); + + pageData->deltaLen += sizeof(header) + sizeof(length); + prevDeltaLen = pageData->deltaLen; + + /* Try building diff delta only if necessary */ + if (!forceBaseDelta) + { + diff = computeRegionDiffDelta(pageData, + curpage, targetpage, + targetStart, targetEnd, + validStart, validEnd); + } + /* + * If we succeeded to make diff delta, just set the header. + * Otherwise, make base delta. + */ + if (diff) + { + header = DIFF_DELTA; + } + else + { + header = BASE_DELTA; + computeRegionBaseDelta(pageData, + curpage, targetpage, + targetStart, targetEnd, + validStart, validEnd); + } + length = pageData->deltaLen - prevDeltaLen; + + writeToPtr(ptr, header); + writeToPtr(ptr, length); +} + +/* + * Compute the XLOG fragments needed to transform a region of curpage into the + * corresponding region of targetpage, and append them to pageData's delta + * field. The region to transform runs from targetStart to targetEnd-1. + * Bytes in curpage outside the range validStart to validEnd-1 should be + * considered invalid, and always overwritten with target data. + * + * This function is a hot spot, so it's worth being as tense as possible + * about the data-matching loops. + */ +static void +computeRegionBaseDelta(PageData *pageData, + const char *curpage, const char *targetpage, + int targetStart, int targetEnd, + int validStart, int validEnd) { int i, loopEnd, @@ -222,27 +339,458 @@ computeRegionDelta(PageData *pageData, } /* + * Align curRegion and targetRegion and return the length of the alignment + * or -1 if the alignment with number of mismatching positions less than + * or equal to MAX_ALIGN_MISMATCHES does not exist. + * The algorithm guarantees to find the alignment with the least possible + * number of mismathing positions or return that such least number is greater + * than MAX_ALIGN_MISMATCHES. + * + * For a good introduction to the subject, read about the "Levenshtein + * distance" in Wikipedia. + * + * The basic algorithm is described in: + * "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers, + * Algorithmica Vol. 1, 1986, pp. 251-266, + * , + * PDF: . + * See especially section 3, which describes the variation used below. + * + * This variation requires O(N + D ^ 2) memory and has time complexity O(ND). + * We choose it because it is faster than described in section 4.2 modification + * with O(N + D) memory requirement. + * + * The only modification we made to the original algorithm is the introduction + * of REPLACE operations, while in the original algorithm only INSERT and + * REMOVE are considered. This introduction doesn't affect time and memory + * complexity of the algorithm. + * + * The alignment is stored in curRegionAligned, targetRegionAligned, + * curRegionAlignedGap and targetRegionAlignedGap. The first two arrays + * contain the aligned data and the second two contain the map of align gaps + * in the first two arrays. + */ +static int +alignRegions(const char *curRegion, const char *targetRegion, + int curRegionLen, int targetRegionLen) +{ + /* Number of mismatches */ + int m; + + /* Difference between curRegion and targetRegion prefix lengths */ + int k; + + /* Curbuf and targetRegion prefix lengths */ + int i, + j; + /* Result alignment length */ + int resLen; + + /* Maximal possible result alignment length */ + int maxResLen; + + /* The length of the equal block */ + int curLen; + + /* Number of mismathes in the answer */ + int numMismatches = -1; + + /* + * If lengths differ too much, there is no alignment with a small + * number of mismatches. + */ + if (!(-MAX_ALIGN_MISMATCHES < curRegionLen - targetRegionLen && + curRegionLen - targetRegionLen < MAX_ALIGN_MISMATCHES)) + return -1; + + /* + * V is an array to store the values of dynamic programming. The first + * dimension corresponds to m, i. e. to the number of performed editing + * operations, and the second one is for k + m, where k is the number of + * a diagonal. + * A diagonal numbered k is such points (i, j) where i - j = k. + * Here i means the length of curRegion prefix and j means the length + * of targetRegion prefix. + * V[m][m + k] is the length of the longest prefix of curRegion i + * which can be aligned with the prefix of length j of targetRegion + * using m editing operations. + * In the loop below we initialize V[0][0] and then compute V[m][m + k] + * based on, if defined, V[m - 1][m + k - 1], V[m - 1][m + k], and + * V[m - 1][m + k + 1]. + * V[m][m + k] is undefined if k < -m or k > m. + */ + V[0][0] = 0; + + /* Find the longest path with the given number of mismatches */ + for (m = 0; m <= MAX_ALIGN_MISMATCHES; ++m) + { + /* + * Find the largest prefix alignment with the given number of + * mismatches and the given diagonal, i. e. difference between + * curRegion and targetRegion prefix lengths. + */ + for (k = -m; k <= m; ++k) + { + /* Dynamic programming recurrent step */ + if (m > 0) + { + i = -1; + if (k != -m && k != m && + V[m - 1][m - 1 + k] + 1 > i) + { + i = V[m - 1][m - 1 + k] + 1; + prevDiag[m][m + k] = k; + } + if (k != -m && k != -m + 1 && + V[m - 1][m - 1 + k - 1] + 1 > i) + { + i = V[m - 1][m - 1 + k - 1] + 1; + prevDiag[m][m + k] = k - 1; + } + if (k != m && k != m - 1 && + V[m - 1][m - 1 + k + 1] > i) + { + i = V[m - 1][m - 1 + k + 1]; + prevDiag[m][m + k] = k + 1; + } + } + else + i = 0; + j = i - k; + + /* Boundary checks */ + Assert(i >= 0); + Assert(j >= 0); + + /* Increase the prefixes while the bytes are equal */ + while (i < curRegionLen && j < targetRegionLen && + curRegion[i] == targetRegion[j]) + i++, j++; + + /* + * Save the largest curRegion prefix that was aligned with given + * number of mismatches and difference between curRegion and + * targetRegion prefix lengths. + */ + V[m][m + k] = i; + + /* If we find the alignment, save its length and break */ + if (i == curRegionLen && j == targetRegionLen) + { + numMismatches = m; + break; + } + } + /* Break if we find an alignment */ + if (numMismatches != -1) + break; + } + /* No alignment was found */ + if (numMismatches == -1) + return -1; + + /* + * Restore the path k-s for each iteration of the main loop + * for the found alignment. + */ + Assert(m >= 0); + while (m != 0) + { + Assert(-m <= k && k <= m); + alignmentDiag[m] = k; + k = prevDiag[m][m + k]; + m--; + } + Assert(k == 0); + alignmentDiag[0] = 0; + + /* Clear RegionAlignedGap arrays */ + maxResLen = Min(curRegionLen, targetRegionLen) + numMismatches; + memset(curRegionAlignedGap, 0, maxResLen); + memset(targetRegionAlignedGap, 0, maxResLen); + + /* Process the first equal block */ + resLen = V[0][0]; + Assert(resLen <= Min(curRegionLen, targetRegionLen)); + memcpy(curRegionAligned, curRegion, V[0][0]); + memcpy(targetRegionAligned, targetRegion, V[0][0]); + + /* Restore the rest of the alignment */ + for (m = 1; m <= numMismatches; ++m) + { + /* Initialize the variables for the block */ + int dk = alignmentDiag[m] - alignmentDiag[m - 1]; + int prevDiag = alignmentDiag[m - 1]; + k = alignmentDiag[m]; + i = V[m - 1][m - 1 + prevDiag]; + j = i - prevDiag; + /* Check state consistency */ + Assert(0 <= i && i <= curRegionLen); + Assert(0 <= j && j <= targetRegionLen); + + /* Check the block operation correctness */ + Assert(dk == -1 || i < curRegionLen); + Assert(dk == 1 || j < targetRegionLen); + Assert(-1 <= dk && dk <= 1); + Assert(resLen + 1 <= maxResLen); + + /* Do the alignment operation of the block */ + if (dk == 1 || dk == 0) + curRegionAligned[resLen] = curRegion[i++]; + else + curRegionAlignedGap[resLen] = true; + if (dk == 0 || dk == -1) + targetRegionAligned[resLen] = targetRegion[j++]; + else + targetRegionAlignedGap[resLen] = true; + resLen++; + + /* Compute the size of the equal part of the block */ + curLen = V[m][m + k] - i; + + /* Check whether the equal part of the block is computed correctly */ + Assert(curLen >= 0); + Assert(resLen + curLen <= maxResLen); + Assert(memcmp(&curRegion[i], &targetRegion[j], curLen) == 0); + + /* Copy the equal part of the block */ + memcpy(&curRegionAligned[resLen], &curRegion[i], curLen); + memcpy(&targetRegionAligned[resLen], &targetRegion[j], curLen); + resLen += curLen; + } + + return resLen; +} + +/* + * Try to build a short alignment in order to produce a short diff delta. + * If fails, return false, otherwise return true and write the delta to + * pageData->delta. + */ +static bool +computeRegionDiffDelta(PageData *pageData, + const char *curpage, const char *targetpage, + int targetStart, int targetEnd, + int validStart, int validEnd) +{ + char *ptr = pageData->delta + pageData->deltaLen; + int i, + j; + char type; + char len; + OffsetNumber start; + OffsetNumber tmp; + + int alignmentLength; + + alignmentLength = alignRegions(&curpage[validStart], + &targetpage[targetStart], + validEnd - validStart, + targetEnd - targetStart); + + /* If no proper alignment was found return false */ + if (alignmentLength < 0) + return false; + + /* + * Translate the alignment into the set of instructions for transformation + * from curRegion into targetRegion, and write these instructions into + * pageData->delta. + */ + + /* Verify we have enough space */ + Assert(pageData->deltaLen + 4 * sizeof(tmp) <= MAX_DELTA_SIZE); + + /* Write start and end indexes of the buffers */ + tmp = validStart; + writeToPtr(ptr, tmp); + tmp = validEnd; + writeToPtr(ptr, tmp); + tmp = targetStart; + writeToPtr(ptr, tmp); + tmp = targetEnd; + writeToPtr(ptr, tmp); + + /* Transform the alignment into the set of instructions */ + start = 0; + for (i = 0; i < alignmentLength; ++i) + { + /* Verify the alignment */ + Assert(!curRegionAlignedGap[i] || !targetRegionAlignedGap[i]); + + /* If the values are equal, write no instructions */ + if (curRegionAligned[i] == targetRegionAligned[i] && + !curRegionAlignedGap[i] && !targetRegionAlignedGap[i]) + { + start++; + continue; + } + + if (curRegionAlignedGap[i]) + type = DIFF_INSERT; + else if (targetRegionAlignedGap[i]) + type = DIFF_REMOVE; + else + type = DIFF_REPLACE; + + /* Find the end of the block of the same instructions */ + j = i + 1; + while (j < alignmentLength) + { + bool sameType = false; + + switch (type) + { + case DIFF_INSERT: + sameType = (curRegionAlignedGap[j]); + break; + case DIFF_REMOVE: + sameType = (targetRegionAlignedGap[j]); + break; + case DIFF_REPLACE: + sameType = (!curRegionAlignedGap[j] && + !targetRegionAlignedGap[j] && + curRegionAligned[j] != targetRegionAligned[j]); + break; + default: + elog(ERROR, "unrecognized delta operation type: %d", type); + break; + } + if (sameType) + j++; + else + break; + } + len = j - i; + + /* Verify we have enough space */ + Assert(pageData->deltaLen + sizeof(type) + + sizeof(len) + sizeof(start) <= MAX_DELTA_SIZE); + /* Write the header for instruction */ + writeToPtr(ptr, type); + writeToPtr(ptr, len); + writeToPtr(ptr, start); + + /* Write instruction data and go to the end of the block */ + if (type != DIFF_REMOVE) + { + /* Verify we have enough space */ + Assert(pageData->deltaLen + len <= MAX_DELTA_SIZE); + while (i < j) + { + char c = targetRegionAligned[i++]; + + writeToPtr(ptr, c); + } + } + else + i = j; + i--; + + /* Shift start position which shows where to apply instruction */ + if (type != DIFF_INSERT) + start += len; + } + + pageData->deltaLen = ptr - pageData->delta; + + return true; +} + +/* + * Return whether pageData->delta contains diff deltas or not. + */ +static bool +pageDataContainsDiffDelta(PageData *pageData) +{ + char *ptr = pageData->delta + sizeof(bool); + char *end = pageData->delta + pageData->deltaLen; + char header; + int length; + + while (ptr < end) + { + readFromPtr(ptr, header); + readFromPtr(ptr, length); + + if (header == DIFF_DELTA) + return true; + ptr += length; + } + return false; +} + +/* + * Downgrade pageData->delta to base delta format. + * + * Only base diffs are allowed to perform the transformation. + */ +static void +downgradeDeltaToBaseFormat(PageData *pageData) +{ + char *ptr = pageData->delta; + char *end = pageData->delta + pageData->deltaLen; + char *cur; + bool containsDiffDelta; + char header; + int length; + int newDeltaLength = 0; + + /* Check whether containsDiffDelta is false */ + readFromPtr(ptr, containsDiffDelta); + Assert(!containsDiffDelta); + + cur = ptr; + while (ptr < end) + { + readFromPtr(ptr, header); + readFromPtr(ptr, length); + + /* Check whether the region delta is base delta */ + Assert(header == BASE_DELTA); + newDeltaLength += length; + + memmove(cur, ptr, length); + cur += length; + ptr += length; + } + pageData->deltaLen = newDeltaLength; +} + +/* * Compute the XLOG delta record needed to transform curpage into targetpage, * and store it in pageData's delta field. */ static void computeDelta(PageData *pageData, Page curpage, Page targetpage) { + bool *containsDiffDelta = pageData->delta; int targetLower = ((PageHeader) targetpage)->pd_lower, targetUpper = ((PageHeader) targetpage)->pd_upper, curLower = ((PageHeader) curpage)->pd_lower, curUpper = ((PageHeader) curpage)->pd_upper; - pageData->deltaLen = 0; + pageData->deltaLen = sizeof(bool); /* Compute delta records for lower part of page ... */ computeRegionDelta(pageData, curpage, targetpage, 0, targetLower, - 0, curLower); + 0, curLower, + false); /* ... and for upper part, ignoring what's between */ computeRegionDelta(pageData, curpage, targetpage, targetUpper, BLCKSZ, - curUpper, BLCKSZ); + curUpper, BLCKSZ, + true); + + /* + * Set first byte to true if at least one of the region deltas + * is diff delta. Otherwise set first byte to false and downgrade all + * regions to base format without extra headers. + */ + *containsDiffDelta = pageDataContainsDiffDelta(pageData); + if (!(*containsDiffDelta)) + downgradeDeltaToBaseFormat(pageData); /* * If xlog debug is enabled, then check produced delta. Result of delta @@ -451,12 +999,58 @@ GenericXLogAbort(GenericXLogState *state) /* * Apply delta to given page image. + * + * Read blocks of instructions and apply them based on their type: + * BASE_DELTA or DIFF_DELTA. */ static void applyPageRedo(Page page, const char *delta, Size deltaSize) { const char *ptr = delta; const char *end = delta + deltaSize; + char header; + int length; + bool containsDiffDelta; + + /* If page delta is base delta, apply it. */ + readFromPtr(ptr, containsDiffDelta); + if (!containsDiffDelta) + { + applyPageBaseRedo(page, ptr, end - ptr); + return; + } + + /* Otherwise apply each region delta. */ + while (ptr < end) + { + readFromPtr(ptr, header); + readFromPtr(ptr, length); + + switch (header) + { + case DIFF_DELTA: + ptr = applyPageDiffRedo(page, ptr, length); + break; + case BASE_DELTA: + ptr = applyPageBaseRedo(page, ptr, length); + break; + default: + elog(ERROR, + "unrecognized delta type: %d", + header); + break; + } + } +} + +/* + * Apply base delta to given page image. + */ +static const char * +applyPageBaseRedo(Page page, const char *delta, Size deltaSize) +{ + const char *ptr = delta; + const char *end = delta + deltaSize; while (ptr < end) { @@ -472,6 +1066,80 @@ applyPageRedo(Page page, const char *delta, Size deltaSize) ptr += length; } + return ptr; +} + +/* + * Apply diff delta to given page image. + */ +static const char * +applyPageDiffRedo(Page page, const char *delta, Size deltaSize) +{ + const char *ptr = delta; + const char *end = delta + deltaSize; + OffsetNumber targetStart, + targetEnd; + OffsetNumber validStart, + validEnd; + int i, + j; + OffsetNumber start; + + /* Read start and end indexes of the buffers */ + readFromPtr(ptr, validStart); + readFromPtr(ptr, validEnd); + readFromPtr(ptr, targetStart); + readFromPtr(ptr, targetEnd); + + /* Read and apply the instructions */ + i = 0, j = 0; + while (ptr < end) + { + char type; + char len; + + /* Read the header of the current instruction */ + readFromPtr(ptr, type); + readFromPtr(ptr, len); + readFromPtr(ptr, start); + + /* Copy the data before current instruction to buffer */ + memcpy(&localPage[j], page + validStart + i, start - i); + j += start - i; + i = start; + + /* Apply the instruction */ + switch (type) + { + case DIFF_INSERT: + memcpy(&localPage[j], ptr, len); + ptr += len; + j += len; + break; + case DIFF_REMOVE: + i += len; + break; + case DIFF_REPLACE: + memcpy(&localPage[j], ptr, len); + i += len; + j += len; + ptr += len; + break; + default: + elog(ERROR, + "unrecognized delta instruction type: %d", + type); + break; + } + } + + /* Copy the data after the last instruction */ + memcpy(&localPage[j], page + validStart + i, validEnd - validStart - i); + j += validEnd - validStart - i; + i = validEnd - validStart; + + memcpy(page + targetStart, localPage, j); + return ptr; } /*