blob: 9ad7a85189c2eeb63b5bcf203ae5ea973974abb1 [file] [log] [blame] [edit]
#!/usr/bin/env bash
# Copyright (c) 2012, Code Aurora Forum. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are
# met:
# # Redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimer.
# # Redistributions in binary form must reproduce the above
# copyright notice, this list of conditions and the following
# disclaimer in the documentation and/or other materials provided
# with the distribution.
# # Neither the name of Code Aurora Forum, Inc. nor the names of its
# contributors may be used to endorse or promote products derived
# from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
# BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
# OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
# IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
usage() { # error_message
cat <<-EOF
usage: $(basename $0) [-unvt] [--noref] [--nolosse] [-r|--ratio number]
[git gc option...] git.repo
-u|-h usage/help
-v verbose
-n dry-run don't actually repack anything
-t touch treat repo as if it had been touched
--noref avoid extra ref packing timestamp checking
--noloose do not run just because there are loose object dirs
(repacking may still run if they are referenced)
-r ratio <number> packfile ratio to aim for (default 10)
git gc option will be passed as args to git gc
git.repo to run gc against
Garbage collect using a pseudo logarithmic packfile maintenance
approach. This approach attempts to minimize packfile churn
by keeping several generations of varying sized packfiles around
and only consolidating packfiles (or loose objects) which are
either new packfiles, or packfiles close to the same size as
another packfile.
An estimate is used to predict when rollups (one consolidation
would cause another consolidation) would occur so that this
rollup can be done all at once via a single repack. This reduces
both the runtime and the pack file churn in rollup cases.
Approach: plan each consolidation by creating a table like this:
Id Keep Size Sha1(or consolidation list) Actions(repack down up note)
1 - 11356 9052edfb7392646cd4e5f362b953675985f01f96 y - - New
2 - 429088 010904d5c11cd26a79fda91b01ab454d1001b402 y - - New
c1 - 440444 [1,2] - - -
Id: numbers preceded by a c are estimated "c pack" files
Keep: - none, k private keep, o our keep
Size: in disk blocks (default du output)
Sha1: of packfile, or consolidation list of packfile ids
Actions
repack: - n no, y yes
down: - noop, ^ consolidate with a file above
up: - noop, v consolidate with a file below
note: Human description of script decisions:
New (file is a new packfile)
Consolidate with:<list of packfile ids>
(too far from:<list of packfile ids>)
On the first pass, always consolidate any new packfiles along
with loose objects and along with any packfiles which are within
the ratio size of their predecessors (note, the list is ordered
by increasing size). After each consolidation, insert a fake
consolidation, or "c pack", to naively represent the size and
ordered positioning of the anticipated new consolidated pack.
Every time a new pack is planned, rescan the list in case the
new "c pack" would cause more consolidation...
Once the packfiles which need consolidation are determined, the
packfiles which will not be consolidated are marked with a .keep
file, and those which will be consolidated will have their .keep
removed if they have one. Thus, the packfiles with a .keep will
not get repacked.
Packfile consolidation is determined by the --ratio parameter
(default is 10). This ratio is somewhat of a tradeoff. The
smaller the number, the more packfiles will be kept on average;
this increases disk utilization somewhat. However, a larger
ratio causes greater churn and may increase disk utilization due
to deleted packfiles not being reclaimed since they may still be
kept open by long running applications such as Gerrit. Sane
ratio values are probably between 2 and 10. Since most
consolidations actually end up smaller than the estimated
consolidated packfile size (due to compression), the true ratio
achieved will likely be 1 to 2 greater than the target ratio.
The smaller the target ratio, the greater this discrepancy.
Finally, attempt to skip garbage collection entirely on untouched
repos. In order to determine if a repo has been touched, use the
timestamp on the script's keep files, if any relevant file/dir
is newer than a keep marker file, assume that the repo has been
touched and gc needs to run. Also assume gc needs to run whenever
there are loose object dirs since they may contain untouched
unreferenced loose objects which need to be pruned (once they
expire).
In order to allow the keep files to be an effective timestamp
marker to detect relevant changes in a repo since the last run,
all relevant files and directories which may be modified during a
gc run (even during a noop gc run), must have their timestamps
reset to the same time as the keep files or gc will always run
even on untouched repos. The relevant files/dirs are all those
files and directories which garbage collection, object packing,
ref packing and pruning might change during noop actions.
EOF
[ -n "$1" ] && info "ERROR $1"
exit 128
}
debug() { [ -n "$SW_V" ] && info "$1" ; }
info() { echo "$1" >&2 ; }
array_copy() { #v2 # array_src array_dst
local src=$1 dst=$2
local s i=0
eval s=\${#$src[@]}
while [ $i -lt $s ] ; do
eval $dst[$i]=\"\${$src[$i]}\"
i=$(($i + 1))
done
}
array_equals() { #v2 # array_name [vals...]
local a=$1 ; shift
local s=0 t=() val
array_copy "$a" t
for s in "${!t[@]}" ; do s=$((s+1)) ; done
[ "$s" -ne "$#" ] && return 1
for val in "${t[@]}" ; do
[ "$val" = "$1" ] || return 2
shift
done
return 0
}
packs_sizes() { # git.repo > "size pack"...
du -s "$1"/objects/pack/pack-$SHA1.pack | sort -n 2> /dev/null
}
is_ourkeep() { grep -q "$KEEP" "$1" 2> /dev/null ; } # keep
has_ourkeep() { is_ourkeep "$(keep_for "$1")" ; } # pack
has_keep() { [ -f "$(keep_for "$1")" ] ; } # pack
is_repo() { [ -d "$1/objects" ] && [ -d "$1/refs/heads" ] ; } # git.repo
keep() { # pack # returns true if we added our keep
keep=$(keep_for "$1")
[ -f "$keep" ] && return 1
echo "$KEEP" > "$keep"
return 0
}
keep_for() { # packfile > keepfile
local keep=$(echo "$1" | sed -es'/\.pack$/.keep/')
[ "${keep/.keep}" = "$keep" ] && return 1
echo "$keep"
}
idx_for() { # packfile > idxfile
local idx=$(echo "$1" | sed -es'/\.pack$/.idx/')
[ "${idx/.idx}" = "$idx" ] && return 1
echo "$idx"
}
# pack_or_keep_file > sha
sha_for() { echo "$1" | sed -es'|\(.*/\)*pack-\([^.]*\)\..*$|\2|' ; }
private_keeps() { # git.repo -> sets pkeeps
local repo=$1 ary=$2
local keep keeps=("$repo"/objects/pack/pack-$SHA1.keep)
pkeeps=()
for keep in "${keeps[@]}" ; do
is_ourkeep "$keep" || pkeeps=("${pkeeps[@]}" "$keep")
done
}
is_tooclose() { [ "$(($1 * $RATIO))" -gt "$2" ] ; } # smaller larger
unique() { # [args...] > unique_words
local lines=$(while [ $# -gt 0 ] ; do echo "$1" ; shift ; done)
lines=$(echo "$lines" | sort -u)
echo $lines # as words
}
outfs() { # fs [args...] > argfs...
local fs=$1 ; shift
[ $# -gt 0 ] && echo -n "$1" ; shift
while [ $# -gt 0 ] ; do echo -n "$fs$1" ; shift ; done
}
sort_list() { # < list > formatted_list
# n has_keep size sha repack down up note
awk '{ note=$8; for(i=8;i<NF;i++) note=note " "$(i+1)
printf("%-5s %s %-14s %-40s %s %s %s %s\n", \
$1,$2, $3, $4, $5,$6,$7,note)}' |\
sort -k 3,3n -k 1,1n
}
is_touched() { # git.repo
local repo=$1
local loose keep ours newer
[ -n "$SW_T" ] && { debug "$SW_T -> treat as touched" ; return 0 ; }
if [ -z "$SW_LOOSE" ] ; then
# If there are loose objects, they may need to be pruned,
# run even if nothing has really been touched.
loose=$(find "$repo/objects" -type d \
-wholename "$repo/objects/[0-9][0-9]"
-print -quit 2>/dev/null)
[ -n "$loose" ] && { info "There are loose object directories" ; return 0 ; }
fi
# If we don't have a keep, the current packfiles may not have been
# compressed with the current gc policy (gc may never have been run),
# so run at least once to repack everything. Also, we need a marker
# file for timestamp tracking (a dir needs to detect changes within
# it, so it cannot be a marker) and our keeps are something we control,
# use them.
for keep in "$repo"/objects/pack/pack-$SHA1.keep ; do
is_ourkeep "$keep" && { ours=$keep ; break ; }
done
[ -z "$ours" ] && { info 'We have no keep (we have never run?): run' ; return 0 ; }
debug "Our timestamp keep: $ours"
# The wholename stuff seems to get touched by a noop git gc
newer=$(find "$repo/objects" "$repo/refs" "$repo/packed-refs" \
'!' -wholename "$repo/objects/info" \
'!' -wholename "$repo/objects/info/*" \
-newer "$ours" \
-print -quit 2>/dev/null)
[ -z "$newer" ] && return 1
info "Touched since last run: $newer"
return 0
}
touch_refs() { # git.repo start_date refs
local repo=$1 start_date=$2 refs=$3
(
debug "Setting start date($start_date) on unpacked refs:"
debug "$refs"
cd "$repo/refs" || return
# safe to assume no newlines in a ref name
echo "$refs" | xargs -d '\n' -n 1 touch -c -d "$start_date"
)
}
set_start_date() { # git.repo start_date refs refdirs packedrefs [packs]
local repo=$1 start_date=$2 refs=$3 refdirs=$4 packedrefs=$5 ; shift 5
local pack keep idx repacked
# This stuff is touched during object packs
while [ $# -gt 0 ] ; do
pack=$1 ; shift
keep="$(keep_for "$pack")"
idx="$(idx_for "$pack")"
touch -c -d "$start_date" "$pack" "$keep" "$idx"
debug "Setting start date on: $pack $keep $idx"
done
# This will prevent us from detecting any deletes in the pack dir
# since gc ran, except for private keeps which we are checking
# manually. But there really shouldn't be any other relevant deletes
# in this dir which should cause us to rerun next time, deleting a
# pack or index file by anything but gc would be bad!
debug "Setting start date on pack dir: $start_date"
touch -c -d "$start_date" "$repo/objects/pack"
if [ -z "$SW_REFS" ] ; then
repacked=$(find "$repo/packed-refs" -newer "$repo/objects/pack"
-print -quit 2>/dev/null)
if [ -n "$repacked" ] ; then
# The ref dirs and packed-ref files seem to get touched even on
# a noop refpacking
debug "Setting start date on packed-refs"
touch -c -d "$start_date" "$repo/packed-refs"
touch_refs "$repo" "$start_date" "$refdirs"
# A ref repack does not imply a ref change, but since it is
# hard to tell, simply assume so
if [ "$refs" != "$(cd "$repo/refs" ; find -depth)" ] || \
[ "$packedrefs" != "$(<"$repo/packed-refs")" ] ; then
# We retouch if needed (instead of simply checking then
# touching) to avoid a race between the check and the set.
debug " but refs actually got packed, so retouch packed-refs"
touch -c "$repo/packed-refs"
fi
fi
fi
}
note_consolidate() { # note entry > note (no duplicated consolidated entries)
local note=$1 entry=$2
local entries=() ifs=$IFS
if echo "$note" | grep -q 'Consolidate with:[0-9,c]' ; then
IFS=,
entries=( $(echo "$note" | sed -es'/^.*Consolidate with:\([0-9,c]*\).*$/\1/') )
note=( $(echo "$note" | sed -es'/Consolidate with:[0-9,c]*//') )
IFS=$ifs
fi
entries=( $(unique "${entries[@]}" "$entry") )
echo "$note Consolidate with:$(outfs , "${entries[@]}")"
}
note_toofar() { # note entry > note (no duplicated "too far" entries)
local note=$1 entry=$2
local entries=() ifs=$IFS
if echo "$note" | grep -q '(too far from:[0-9,c]*)' ; then
IFS=,
entries=( $(echo "$note" | sed -es'/^.*(too far from:\([0-9,c]*\)).*$/\1/') )
note=( $(echo "$note" | sed -es'/(too far from:[0-9,c]*)//') )
IFS=$ifs
fi
entries=( $(unique "${entries[@]}" "$entry") )
echo "$note (too far from:$(outfs , "${entries[@]}"))"
}
last_entry() { # isRepack pline repackline > last_rows_entry
local size_hit=$1 pline=$2 repackline=$3
if [ -n "$pline" ] ; then
if [ -n "$size_hit" ] ; then
echo "$repack_line"
else
echo "$pline"
fi
fi
}
init_list() { # git.repo > shortlist
local repo=$1
local file
local n has_keep size sha repack
packs_sizes "$1" | {
while read size file ; do
n=$((n+1))
repack=n
has_keep=-
if has_keep "$file" ; then
has_keep=k
has_ourkeep "$file" && has_keep=o
fi
sha=$(sha_for "$file")
echo "$n $has_keep $size $sha $repack"
done
} | sort_list
}
consolidate_list() { # run < list > list
local run=$1
local sum=0 psize=0 sum_size=0 size_hit pn clist pline repackline
local n has_keep size sha repack down up note
{
while read n has_keep size sha repack down up note; do
[ -z "$up" ] && up='-'
[ -z "$down" ] && down="-"
if [ "$has_keep" = "k" ] ; then
echo "$n $has_keep $size $sha $repack - - Private"
continue
fi
if [ "$repack" = "n" ] ; then
if is_tooclose $psize $size ; then
size_hit=y
repack=y
sum=$(($sum + $sum_size + $size))
sum_size=0 # Prevents double summing this entry
clist=($(unique "${clist[@]}" $pn $n))
down="^"
[ "$has_keep" = "-" ] && note="$note New +"
note=$(note_consolidate "$note" "$pn")
elif [ "$has_keep" = "-" ] ; then
repack=y
sum=$(($sum + $size))
sum_size=0 # Prevents double summing this entry
clist=($(unique "${clist[@]}" $n))
note="$note New"
elif [ $psize -ne 0 ] ; then
sum_size=$size
down="!"
note=$(note_toofar "$note" "$pn")
else
sum_size=$size
fi
else
sum_size=$size
fi
# By preventing "c files" (consolidated) from being marked
# "repack" they won't get keeps
repack2=y
[ "${n/c}" != "$n" ] && { repack=- ; repack2=- ; }
last_entry "$size_hit" "$pline" "$repack_line"
# Delay the printout until we know whether we are
# being consolidated with the entry following us
# (we won't know until the next iteration).
# size_hit is used to determine which of the lines
# below will actually get printed above on the next
# iteration.
pline="$n $has_keep $size $sha $repack $down $up $note"
repack_line="$n $has_keep $size $sha $repack2 $down v $note"
pn=$n ; psize=$size # previous entry data
size_hit='' # will not be consolidated up
done
last_entry "$size_hit" "$pline" "$repack_line"
[ $sum -gt 0 ] && echo "c$run - $sum [$(outfs , "${clist[@]}")] - - -"
} | sort_list
}
process_list() { # git.repo > list
local list=$(init_list "$1") plist run=0
while true ; do
plist=$list
run=$((run +1))
list=$(echo "$list" | consolidate_list "$run")
if [ "$plist" != "$list" ] ; then
debug "------------------------------------------------------------------------------------"
debug "$HEADER"
debug "$list"
else
break
fi
done
debug "------------------------------------------------------------------------------------"
echo "$list"
}
repack_list() { # git.repo < list
local repo=$1
local start_date newpacks=0 pkeeps keeps=1 refs refdirs rtn
local packedrefs=$(<"$repo/packed-refs")
# so they don't appear touched after a noop refpacking
if [ -z "$SW_REFS" ] ; then
refs=$(cd "$repo/refs" ; find -depth)
refdirs=$(cd "$repo/refs" ; find -type d -depth)
debug "Before refs:"
debug "$refs"
fi
# Find a private keep snapshot which has not changed from
# before our start_date so private keep deletions during gc
# can be detected
while ! array_equals pkeeps "${keeps[@]}" ; do
debug "Getting a private keep snapshot"
private_keeps "$repo"
keeps=("${pkeeps[@]}")
debug "before keeps: ${keeps[*]}"
start_date=$(date)
private_keeps "$repo"
debug "after keeps: ${pkeeps[*]}"
done
while read n has_keep size sha repack down up note; do
if [ "$repack" = "y" ] ; then
keep="$repo/objects/pack/pack-$sha.keep"
info "Repacking $repo/objects/pack/pack-$sha.pack"
[ -f "$keep" ] && rm -f "$keep"
fi
done
( cd "$repo" && git gc "${GC_OPTS[@]}" ) ; rtn=$?
# Mark any files withoug a .keep with our .keep
packs=("$repo"/objects/pack/pack-$SHA1.pack)
for pack in "${packs[@]}" ; do
if keep "$pack" ; then
info "New pack: $pack"
newpacks=$((newpacks+1))
fi
done
# Record start_time. If there is more than 1 new packfile, we
# don't want to risk touching it with an older date since that
# would prevent consolidation on the next run. If the private
# keeps have changed, then we should run next time no matter what.
if [ $newpacks -le 1 ] || ! array_equals pkeeps "${keeps[@]}" ; then
set_start_date "$repo" "$start_date" "$refs" "$refdirs" "$packedrefs" "${packs[@]}"
fi
return $rtn # we really only care about the gc error code
}
git_gc() { # git.repo
local list=$(process_list "$1")
if [ -z "$SW_V" ] ; then
info "Running $PROG on $1. git gc options: ${GC_OPTS[@]}"
echo "$HEADER" >&2
echo "$list" >&2 ;
fi
echo "$list" | repack_list "$1"
}
PROG=$(basename "$0")
HEADER="Id Keep Size Sha1(or consolidation list) Actions(repack down up note)"
KEEP=git-exproll
HEX='[0-9a-f]'
HEX10=$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX
SHA1=$HEX10$HEX10$HEX10$HEX10
RATIO=10
SW_N='' ; SW_V='' ; SW_T='' ; SW_REFS='' ; SW_LOOSE='' ; GC_OPTS=()
while [ $# -gt 0 ] ; do
case "$1" in
-u|-h) usage ;;
-n) SW_N="$1" ;;
-v) SW_V="$1" ;;
-t) SW_T="$1" ;;
--norefs) SW_REFS="$1" ;;
--noloose) SW_LOOSE="$1" ;;
-r|--ratio) shift ; RATIO="$1" ;;
*) [ $# -le 1 ] && break
GC_OPTS=( "${GC_OPTS[@]}" "$1" )
;;
esac
shift
done
REPO="$1"
if ! is_repo "$REPO" ; then
REPO=$REPO/.git
is_repo "$REPO" || usage "($1) is not likely a git repo"
fi
if [ -z "$SW_N" ] ; then
is_touched "$REPO" || { info "Repo untouched since last run" ; exit ; }
git_gc "$REPO"
else
is_touched "$REPO" || info "Repo untouched since last run, analyze anyway."
process_list "$REPO" >&2
fi