Merge pull request #6863 from owncloud/versioning_expire_function_tests

Versioning expire function tests

2 files changed, 264 insertions, 77 deletions

diff --git a/apps/files_versions/lib/versions.php b/apps/files_versions/lib/versions.php
index 01c2e1ccdee..8463bd9482c 100644
--- a/apps/files_versions/lib/versions.php
+++ b/apps/files_versions/lib/versions.php
@@ -418,6 +418,65 @@ class Storage {
 	}
 
 	/**
+	 * @brief get list of files we want to expire
+	 * @param int $currentTime timestamp of current time
+	 * @param array $versions list of versions
+	 * @return array containing the list of to deleted versions and the size of them
+	 */
+	protected static function getExpireList($time, $versions) {
+
+		$size = 0;
+		$toDelete = array();  // versions we want to delete
+
+		$versions = array_reverse($versions); // newest version first
+
+		$interval = 1;
+		$step = Storage::$max_versions_per_interval[$interval]['step'];
+		if (Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'] == -1) {
+			$nextInterval = -1;
+		} else {
+			$nextInterval = $time - Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'];
+		}
+
+		$firstVersion = reset($versions);
+		$firstKey = key($versions);
+		$prevTimestamp = $firstVersion['version'];
+		$nextVersion = $firstVersion['version'] - $step;
+		unset($versions[$firstKey]);
+
+		foreach ($versions as $key => $version) {
+			$newInterval = true;
+			while ($newInterval) {
+				if ($nextInterval == -1 || $prevTimestamp > $nextInterval) {
+					if ($version['version'] > $nextVersion) {
+						//distance between two version too small, mark to delete
+						$toDelete[$key] = $version['path'] . '.v' . $version['version'];
+						$size += $version['size'];
+						\OCP\Util::writeLog('files_versions', 'Mark to expire '. $version['path'] .' next version should be ' . $nextVersion . " or smaller. (prevTimestamp: " . $prevTimestamp . "; step: " . $step, \OCP\Util::DEBUG);
+					} else {
+						$nextVersion = $version['version'] - $step;
+						$prevTimestamp = $version['version'];
+					}
+					$newInterval = false; // version checked so we can move to the next one
+				} else { // time to move on to the next interval
+					$interval++;
+					$step = Storage::$max_versions_per_interval[$interval]['step'];
+					$nextVersion = $prevTimestamp - $step;
+					if (Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'] == -1) {
+						$nextInterval = -1;
+					} else {
+						$nextInterval = $time - Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'];
+					}
+					$newInterval = true; // we changed the interval -> check same version with new interval
+				}
+			}
+		}
+
+		return array($toDelete, $size);
+
+	}
+
+	/**
 	 * @brief Erase a file's versions which exceed the set quota
 	 */
 	private static function expire($filename, $versionsSize = null, $offset = 0) {
@@ -461,33 +520,35 @@ class Storage {
 				$availableSpace = $quota - $offset;
 			}
 
-
-			// with the  probability of 0.1% we reduce the number of all versions not only for the current file
-			$random = rand(0, 1000);
-			if ($random == 0) {
-				$allFiles = true;
-			} else {
-				$allFiles = false;
-			}
-
 			$allVersions = Storage::getVersions($uid, $filename);
-			$versionsByFile[$filename] = $allVersions;
 
-			$sizeOfDeletedVersions = self::delOldVersions($versionsByFile, $allVersions, $versionsFileview);
+			$time = time();
+			list($toDelete, $sizeOfDeletedVersions) = self::getExpireList($time, $allVersions);
+
 			$availableSpace = $availableSpace + $sizeOfDeletedVersions;
 			$versionsSize = $versionsSize - $sizeOfDeletedVersions;
 
 			// if still not enough free space we rearrange the versions from all files
-			if ($availableSpace <= 0 || $allFiles) {
+			if ($availableSpace <= 0) {
 				$result = Storage::getAllVersions($uid);
-				$versionsByFile = $result['by_file'];
 				$allVersions = $result['all'];
 
-				$sizeOfDeletedVersions = self::delOldVersions($versionsByFile, $allVersions, $versionsFileview);
+				foreach ($result['by_file'] as $versions) {
+					list($toDeleteNew, $size) = self::getExpireList($time, $versions);
+					$toDelete = array_merge($toDelete, $toDeleteNew);
+					$sizeOfDeletedVersions += $size;
+				}
 				$availableSpace = $availableSpace + $sizeOfDeletedVersions;
 				$versionsSize = $versionsSize - $sizeOfDeletedVersions;
 			}
 
+			foreach($toDelete as $key => $path) {
+				\OC_Hook::emit('\OCP\Versions', 'delete', array('path' => $path));
+				$versionsFileview->unlink($path);
+				unset($allVersions[$key]); // update array with the versions we keep
+				\OCP\Util::writeLog('files_versions', "Expire: " . $path, \OCP\Util::DEBUG);
+			}
+
 			// Check if enough space is available after versions are rearranged.
 			// If not we delete the oldest versions until we meet the size limit for versions,
 			// but always keep the two latest versions
@@ -497,6 +558,7 @@ class Storage {
 				$version = current($allVersions);
 				$versionsFileview->unlink($version['path'].'.v'.$version['version']);
 				\OC_Hook::emit('\OCP\Versions', 'delete', array('path' => $version['path'].'.v'.$version['version']));
+				\OCP\Util::writeLog('files_versions', 'running out of space! Delete oldest version: ' . $version['path'].'.v'.$version['version'] , \OCP\Util::DEBUG);
 				$versionsSize -= $version['size'];
 				$availableSpace += $version['size'];
 				next($allVersions);
@@ -510,69 +572,6 @@ class Storage {
 	}
 
 	/**
-	 * @brief delete old version from a given list of versions
-	 *
-	 * @param array $versionsByFile list of versions ordered by files
-	 * @param array $allVversions all versions across multiple files
-	 * @param $versionsFileview \OC\Files\View on data/user/files_versions
-	 * @return size of releted versions
-	 */
-	private static function delOldVersions($versionsByFile, &$allVersions, $versionsFileview) {
-
-		$time = time();
-		$size = 0;
-
-		// delete old versions for every given file
-		foreach ($versionsByFile as $versions) {
-			$versions = array_reverse($versions); // newest version first
-
-			$interval = 1;
-			$step = Storage::$max_versions_per_interval[$interval]['step'];
-			if (Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'] == -1) {
-				$nextInterval = -1;
-			} else {
-				$nextInterval = $time - Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'];
-			}
-
-			$firstVersion = reset($versions);
-			$firstKey = key($versions);
-			$prevTimestamp = $firstVersion['version'];
-			$nextVersion = $firstVersion['version'] - $step;
-			unset($versions[$firstKey]);
-
-			foreach ($versions as $key => $version) {
-				$newInterval = true;
-				while ($newInterval) {
-					if ($nextInterval == -1 || $version['version'] >= $nextInterval) {
-						if ($version['version'] > $nextVersion) {
-							//distance between two version too small, delete version
-							$versionsFileview->unlink($version['path'] . '.v' . $version['version']);
-							\OC_Hook::emit('\OCP\Versions', 'delete', array('path' => $version['path'] . '.v' . $version['version']));
-							$size += $version['size'];
-							unset($allVersions[$key]); // update array with all versions
-						} else {
-							$nextVersion = $version['version'] - $step;
-						}
-						$newInterval = false; // version checked so we can move to the next one
-					} else { // time to move on to the next interval
-						$interval++;
-						$step = Storage::$max_versions_per_interval[$interval]['step'];
-						$nextVersion = $prevTimestamp - $step;
-						if (Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'] == -1) {
-							$nextInterval = -1;
-						} else {
-							$nextInterval = $time - Storage::$max_versions_per_interval[$interval]['intervalEndsAfter'];
-						}
-						$newInterval = true; // we changed the interval -> check same version with new interval
-					}
-				}
-				$prevTimestamp = $version['version'];
-			}
-		}
-		return $size;
-	}
-
-	/**
 	 * @brief create recursively missing directories
 	 * @param string $filename $path to a file
 	 * @param \OC\Files\View $view view on data/user/
diff --git a/apps/files_versions/tests/versions.php b/apps/files_versions/tests/versions.php
new file mode 100644
index 00000000000..713f7796c9b
--- /dev/null
+++ b/apps/files_versions/tests/versions.php
@@ -0,0 +1,188 @@
+<?php
+/**
+ * ownCloud
+ *
+ * @author Bjoern Schiessle
+ * @copyright 2014 Bjoern Schiessle <schiessle@owncloud.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU AFFERO GENERAL PUBLIC LICENSE
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or any later version.
+ *
+ * This library 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 AFFERO GENERAL PUBLIC LICENSE for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public
+ * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+require_once __DIR__ . '/../lib/versions.php';
+
+/**
+ * Class Test_Files_versions
+ * @brief this class provide basic files versions test
+ */
+class Test_Files_Versioning extends \PHPUnit_Framework_TestCase {
+
+
+	/**
+	 * @medium
+	 * @brief test expire logic
+	 * @dataProvider versionsProvider
+	 */
+	function testGetExpireList($versions, $sizeOfAllDeletedFiles) {
+
+		// last interval enda at 2592000
+		$startTime = 5000000;
+
+		$testClass = new VersionStorageToTest();
+		list($deleted, $size) = $testClass->callProtectedGetExpireList($startTime, array_reverse($versions));
+
+		// we should have deleted 16 files each of the size 1
+		$this->assertEquals($sizeOfAllDeletedFiles, $size);
+
+		// the deleted array should only contain versions which should be deleted
+		foreach($deleted as $key => $path) {
+			unset($versions[$key]);
+			$this->assertEquals("delete", substr($path, 0, strlen("delete")));
+		}
+
+		// the versions array should only contain versions which should be kept
+		foreach ($versions as $version) {
+			$this->assertEquals("keep", $version['path']);
+		}
+
+	}
+
+	public function versionsProvider() {
+		return array(
+			// first set of versions uniformly distributed versions
+			array(
+				array(
+					// first slice (10sec) keep one version every 2 seconds
+					array("version" => 4999999, "path" => "keep", "size" => 1),
+					array("version" => 4999998, "path" => "delete", "size" => 1),
+					array("version" => 4999997, "path" => "keep", "size" => 1),
+					array("version" => 4999995, "path" => "keep", "size" => 1),
+					array("version" => 4999994, "path" => "delete", "size" => 1),
+					//next slice (60sec) starts at 4999990 keep one version every 10 secons
+					array("version" => 4999988, "path" => "keep", "size" => 1),
+					array("version" => 4999978, "path" => "keep", "size" => 1),
+					array("version" => 4999975, "path" => "delete", "size" => 1),
+					array("version" => 4999972, "path" => "delete", "size" => 1),
+					array("version" => 4999967, "path" => "keep", "size" => 1),
+					array("version" => 4999958, "path" => "delete", "size" => 1),
+					array("version" => 4999957, "path" => "keep", "size" => 1),
+					//next slice (3600sec) start at 4999940 keep one version every 60 seconds
+					array("version" => 4999900, "path" => "keep", "size" => 1),
+					array("version" => 4999841, "path" => "delete", "size" => 1),
+					array("version" => 4999840, "path" => "keep", "size" => 1),
+					array("version" => 4999780, "path" => "keep", "size" => 1),
+					array("version" => 4996401, "path" => "keep", "size" => 1),
+					// next slice (86400sec) start at 4996400 keep one version every 3600 seconds
+					array("version" => 4996350, "path" => "delete", "size" => 1),
+					array("version" => 4992800, "path" => "keep", "size" => 1),
+					array("version" => 4989800, "path" => "delete", "size" => 1),
+					array("version" => 4989700, "path" => "delete", "size" => 1),
+					array("version" => 4989200, "path" => "keep", "size" => 1),
+					// next slice (2592000sec) start at 4913600 keep one version every 86400 seconds
+					array("version" => 4913600, "path" => "keep", "size" => 1),
+					array("version" => 4852800, "path" => "delete", "size" => 1),
+					array("version" => 4827201, "path" => "delete", "size" => 1),
+					array("version" => 4827200, "path" => "keep", "size" => 1),
+					array("version" => 4777201, "path" => "delete", "size" => 1),
+					array("version" => 4777501, "path" => "delete", "size" => 1),
+					array("version" => 4740000, "path" => "keep", "size" => 1),
+					// final slice starts at 2408000 keep one version every 604800 secons
+					array("version" => 2408000, "path" => "keep", "size" => 1),
+					array("version" => 1803201, "path" => "delete", "size" => 1),
+					array("version" => 1803200, "path" => "keep", "size" => 1),
+					array("version" => 1800199, "path" => "delete", "size" => 1),
+					array("version" => 1800100, "path" => "delete", "size" => 1),
+					array("version" => 1198300, "path" => "keep", "size" => 1),
+				),
+				16 // size of all deleted files (every file has the size 1)
+			),
+			// second set of versions, here we have only really old versions
+			array(
+				array(
+					// first slice (10sec) keep one version every 2 seconds
+					// next slice (60sec) starts at 4999990 keep one version every 10 secons
+					// next slice (3600sec) start at 4999940 keep one version every 60 seconds
+					// next slice (86400sec) start at 4996400 keep one version every 3600 seconds
+					array("version" => 4996400, "path" => "keep", "size" => 1),
+					array("version" => 4996350, "path" => "delete", "size" => 1),
+					array("version" => 4996350, "path" => "delete", "size" => 1),
+					array("version" => 4992800, "path" => "keep", "size" => 1),
+					array("version" => 4989800, "path" => "delete", "size" => 1),
+					array("version" => 4989700, "path" => "delete", "size" => 1),
+					array("version" => 4989200, "path" => "keep", "size" => 1),
+					// next slice (2592000sec) start at 4913600 keep one version every 86400 seconds
+					array("version" => 4913600, "path" => "keep", "size" => 1),
+					array("version" => 4852800, "path" => "delete", "size" => 1),
+					array("version" => 4827201, "path" => "delete", "size" => 1),
+					array("version" => 4827200, "path" => "keep", "size" => 1),
+					array("version" => 4777201, "path" => "delete", "size" => 1),
+					array("version" => 4777501, "path" => "delete", "size" => 1),
+					array("version" => 4740000, "path" => "keep", "size" => 1),
+					// final slice starts at 2408000 keep one version every 604800 secons
+					array("version" => 2408000, "path" => "keep", "size" => 1),
+					array("version" => 1803201, "path" => "delete", "size" => 1),
+					array("version" => 1803200, "path" => "keep", "size" => 1),
+					array("version" => 1800199, "path" => "delete", "size" => 1),
+					array("version" => 1800100, "path" => "delete", "size" => 1),
+					array("version" => 1198300, "path" => "keep", "size" => 1),
+				),
+				11 // size of all deleted files (every file has the size 1)
+			),
+			// third set of versions, with some gaps inbetween
+			array(
+				array(
+					// first slice (10sec) keep one version every 2 seconds
+					array("version" => 4999999, "path" => "keep", "size" => 1),
+					array("version" => 4999998, "path" => "delete", "size" => 1),
+					array("version" => 4999997, "path" => "keep", "size" => 1),
+					array("version" => 4999995, "path" => "keep", "size" => 1),
+					array("version" => 4999994, "path" => "delete", "size" => 1),
+					//next slice (60sec) starts at 4999990 keep one version every 10 secons
+					array("version" => 4999988, "path" => "keep", "size" => 1),
+					array("version" => 4999978, "path" => "keep", "size" => 1),
+					//next slice (3600sec) start at 4999940 keep one version every 60 seconds
+					// next slice (86400sec) start at 4996400 keep one version every 3600 seconds
+					array("version" => 4989200, "path" => "keep", "size" => 1),
+					// next slice (2592000sec) start at 4913600 keep one version every 86400 seconds
+					array("version" => 4913600, "path" => "keep", "size" => 1),
+					array("version" => 4852800, "path" => "delete", "size" => 1),
+					array("version" => 4827201, "path" => "delete", "size" => 1),
+					array("version" => 4827200, "path" => "keep", "size" => 1),
+					array("version" => 4777201, "path" => "delete", "size" => 1),
+					array("version" => 4777501, "path" => "delete", "size" => 1),
+					array("version" => 4740000, "path" => "keep", "size" => 1),
+					// final slice starts at 2408000 keep one version every 604800 secons
+					array("version" => 2408000, "path" => "keep", "size" => 1),
+					array("version" => 1803201, "path" => "delete", "size" => 1),
+					array("version" => 1803200, "path" => "keep", "size" => 1),
+					array("version" => 1800199, "path" => "delete", "size" => 1),
+					array("version" => 1800100, "path" => "delete", "size" => 1),
+					array("version" => 1198300, "path" => "keep", "size" => 1),
+				),
+				9 // size of all deleted files (every file has the size 1)
+			),
+
+		);
+	}
+
+}
+
+// extend the original class to make it possible to test protected methods
+class VersionStorageToTest extends \OCA\Files_Versions\Storage {
+
+	public function callProtectedGetExpireList($time, $versions) {
+		return self::getExpireList($time, $versions);
+
+	}
+}