%% This Source Code Form is subject to the terms of the Mozilla Public
%% License, v. 2.0. If a copy of the MPL was not distributed with this
%% file, You can obtain one at https://mozilla.org/MPL/2.0/.
%%
%% Copyright (c) 2007-2024 Broadcom. All Rights Reserved. The term “Broadcom” refers to Broadcom Inc. and/or its subsidiaries.  All rights reserved.
%%

-module(rabbit_queue_index).

-compile({inline, [segment_entry_count/0]}).

-export([erase/1, init/3, reset_state/1, recover/7,
         terminate/3, delete_and_terminate/1, info/1,
         pre_publish/7, flush_pre_publish_cache/2,
         publish/7, publish/8, deliver/2, ack/2, sync/1, needs_sync/1, flush/1,
         read/3, next_segment_boundary/1, bounds/1, start/2, stop/1]).

%% Used by rabbit_vhost to set the segment_entry_count.
-export([all_queue_directory_names/1]).

%% Used by rabbit_classic_queue_index_v2 when upgrading
%% after a non-clean shutdown.
-export([queue_index_walker_reader/2]).

%% Used to upgrade/downgrade to/from the v2 index.
-export([init_args/1]).
-export([init_for_conversion/3]).
-export([delete_segment_file_for_seq_id/2]).
-export([delete_journal/1]).

-define(CLEAN_FILENAME, "clean.dot").

%%----------------------------------------------------------------------------

%% The queue index is responsible for recording the order of messages
%% within a queue on disk. As such it contains records of messages
%% being published, delivered and acknowledged. The publish record
%% includes the sequence ID, message ID and a small quantity of
%% metadata about the message; the delivery and acknowledgement
%% records just contain the sequence ID. A publish record may also
%% contain the complete message if provided to publish/5; this allows
%% the message store to be avoided altogether for small messages. In
%% either case the publish record is stored in memory in the same
%% serialised format it will take on disk.
%%
%% Because of the fact that the queue can decide at any point to send
%% a queue entry to disk, you can not rely on publishes appearing in
%% order. The only thing you can rely on is a message being published,
%% then delivered, then ack'd.
%%
%% In order to be able to clean up ack'd messages, we write to segment
%% files. These files have a fixed number of entries: segment_entry_count()
%% publishes, delivers and acknowledgements. They are numbered, and so
%% it is known that the 0th segment contains messages 0 ->
%% segment_entry_count() - 1, the 1st segment contains messages
%% segment_entry_count() -> 2*segment_entry_count() - 1 and so on. As
%% such, in the segment files, we only refer to message sequence ids
%% by the LSBs as SeqId rem segment_entry_count(). This gives them a
%% fixed size.
%%
%% However, transient messages which are not sent to disk at any point
%% will cause gaps to appear in segment files. Therefore, we delete a
%% segment file whenever the number of publishes == number of acks
%% (note that although it is not fully enforced, it is assumed that a
%% message will never be ackd before it is delivered, thus this test
%% also implies == number of delivers). In practise, this does not
%% cause disk churn in the pathological case because of the journal
%% and caching (see below).
%%
%% Because of the fact that publishes, delivers and acks can occur all
%% over, we wish to avoid lots of seeking. Therefore we have a fixed
%% sized journal to which all actions are appended. When the number of
%% entries in this journal reaches max_journal_entries, the journal
%% entries are scattered out to their relevant files, and the journal
%% is truncated to zero size. Note that entries in the journal must
%% carry the full sequence id, thus the format of entries in the
%% journal is different to that in the segments.
%%
%% The journal is also kept fully in memory, pre-segmented: the state
%% contains a mapping from segment numbers to state-per-segment (this
%% state is held for all segments which have been "seen": thus a
%% segment which has been read but has no pending entries in the
%% journal is still held in this mapping. Also note that a map is
%% used for this mapping, not an array because with an array, you will
%% always have entries from 0). Actions are stored directly in this
%% state. Thus at the point of flushing the journal, firstly no
%% reading from disk is necessary, but secondly if the known number of
%% acks and publishes in a segment are equal, given the known state of
%% the segment file combined with the journal, no writing needs to be
%% done to the segment file either (in fact it is deleted if it exists
%% at all). This is safe given that the set of acks is a subset of the
%% set of publishes. When it is necessary to sync messages, it is
%% sufficient to fsync on the journal: when entries are distributed
%% from the journal to segment files, those segments appended to are
%% fsync'd prior to the journal being truncated.
%%
%% This module is also responsible for scanning the queue index files
%% and seeding the message store on start up.
%%
%% Note that in general, the representation of a message's state as
%% the tuple: {('no_pub'|{IsPersistent, Bin, MsgBin}),
%% ('del'|'no_del'), ('ack'|'no_ack')} is richer than strictly
%% necessary for most operations. However, for startup, and to ensure
%% the safe and correct combination of journal entries with entries
%% read from the segment on disk, this richer representation vastly
%% simplifies and clarifies the code.
%%
%% For notes on Clean Shutdown and startup, see documentation in
%% rabbit_variable_queue.
%%
%% v2 UPDATE: The queue index is still keeping track of delivers
%% as noted in the above comment. However the queue will immediately
%% mark messages as delivered, because it now keeps track of delivers
%% at the queue level. The index still needs to keep track of deliver
%% entries because of its pub->del->ack logic.
%%
%%----------------------------------------------------------------------------

%% ---- Journal details ----

-define(JOURNAL_FILENAME, "journal.jif").
-define(QUEUE_NAME_STUB_FILE, ".queue_name").

-define(PUB_PERSIST_JPREFIX, 2#00).
-define(PUB_TRANS_JPREFIX,   2#01).
-define(DEL_JPREFIX,         2#10).
-define(ACK_JPREFIX,         2#11).
-define(JPREFIX_BITS, 2).
-define(SEQ_BYTES, 8).
-define(SEQ_BITS, ((?SEQ_BYTES * 8) - ?JPREFIX_BITS)).

%% ---- Segment details ----

-define(SEGMENT_EXTENSION, ".idx").

%% TODO: The segment size would be configurable, but deriving all the
%% other values is quite hairy and quite possibly noticeably less
%% efficient, depending on how clever the compiler is when it comes to
%% binary generation/matching with constant vs variable lengths.

-define(REL_SEQ_BITS, 14).

%% seq only is binary 01 followed by 14 bits of rel seq id
%% (range: 0 - 16383)
-define(REL_SEQ_ONLY_PREFIX, 01).
-define(REL_SEQ_ONLY_PREFIX_BITS, 2).
-define(REL_SEQ_ONLY_RECORD_BYTES, 2).

%% publish record is binary 1 followed by a bit for is_persistent,
%% then 14 bits of rel seq id, 64 bits for message expiry, 32 bits of
%% size and then 128 bits of md5sum msg id.
-define(PUB_PREFIX, 1).
-define(PUB_PREFIX_BITS, 1).

-define(EXPIRY_BYTES, 8).
-define(EXPIRY_BITS, (?EXPIRY_BYTES * 8)).
-define(NO_EXPIRY, 0).

-define(MSG_ID_BYTES, 16). %% md5sum is 128 bit or 16 bytes
-define(MSG_ID_BITS, (?MSG_ID_BYTES * 8)).

%% This is the size of the message body content, for stats
-define(SIZE_BYTES, 4).
-define(SIZE_BITS, (?SIZE_BYTES * 8)).

%% This is the size of the message record embedded in the queue
%% index. If 0, the message can be found in the message store.
-define(EMBEDDED_SIZE_BYTES, 4).
-define(EMBEDDED_SIZE_BITS, (?EMBEDDED_SIZE_BYTES * 8)).

%% 16 bytes for md5sum + 8 for expiry
-define(PUB_RECORD_BODY_BYTES, (?MSG_ID_BYTES + ?EXPIRY_BYTES + ?SIZE_BYTES)).
%% + 4 for size
-define(PUB_RECORD_SIZE_BYTES, (?PUB_RECORD_BODY_BYTES + ?EMBEDDED_SIZE_BYTES)).

%% + 2 for seq, bits and prefix
-define(PUB_RECORD_PREFIX_BYTES, 2).

%% ---- misc ----

-define(PUB, {_, _, _}). %% {IsPersistent, Bin, MsgBin}

-define(READ_MODE, [binary, raw, read]).
-define(WRITE_MODE, [write | ?READ_MODE]).

%%----------------------------------------------------------------------------

-record(qistate, {
  %% queue directory where segment and journal files are stored
  dir,
  %% map of #segment records
  segments,
  %% journal file handle obtained from/used by file_handle_cache
  journal_handle,
  %% how many not yet flushed entries are there
  dirty_count,
  %% this many not yet flushed journal entries will force a flush
  max_journal_entries,
  %% callback function invoked when a message is "handled"
  %% by the index and potentially can be confirmed to the publisher
  on_sync,
  on_sync_msg,
  %% set of IDs of unconfirmed [to publishers] messages
  unconfirmed,
  unconfirmed_msg,
  %% optimisation
  pre_publish_cache,
  %% optimisation
  delivered_cache,
  %% queue name resource record
  queue_name}).

-record(segment, {
  %% segment ID (an integer)
  num,
  %% segment file path (see also ?SEGMENT_EXTENSION)
  path,
  %% index operation log entries in this segment
  journal_entries,
  entries_to_segment,
  %% counter of unacknowledged messages
  unacked
}).

-include_lib("rabbit_common/include/rabbit.hrl").

%%----------------------------------------------------------------------------

-type hdl() :: ('undefined' | any()).
-type segment() :: ('undefined' |
                    #segment { num                :: non_neg_integer(),
                               path               :: file:filename(),
                               journal_entries    :: array:array(),
                               entries_to_segment :: array:array(),
                               unacked            :: non_neg_integer()
                             }).
-type seg_map() :: {map(), [segment()]}.
-type on_sync_fun() :: fun ((sets:set()) -> ok).
-type qistate() :: #qistate { dir                 :: file:filename(),
                              segments            :: 'undefined' | seg_map(),
                              journal_handle      :: hdl(),
                              dirty_count         :: integer(),
                              max_journal_entries :: non_neg_integer(),
                              on_sync             :: on_sync_fun(),
                              on_sync_msg         :: on_sync_fun(),
                              unconfirmed         :: sets:set(),
                              unconfirmed_msg     :: sets:set(),
                              pre_publish_cache   :: list(),
                              delivered_cache     :: list()
                            }.
-type contains_predicate() :: fun ((rabbit_types:msg_id()) -> boolean()).
-type walker(A) :: fun ((A) -> 'finished' |
                               {rabbit_types:msg_id(), non_neg_integer(), A}).
-type shutdown_terms() :: [term()] | 'non_clean_shutdown'.

%%----------------------------------------------------------------------------
%% public API
%%----------------------------------------------------------------------------

-spec erase(rabbit_amqqueue:name()) -> 'ok'.

erase(#resource{ virtual_host = VHost } = Name) ->
    VHostDir = rabbit_vhost:msg_store_dir_path(VHost),
    #qistate { dir = Dir } = blank_state(VHostDir, Name),
    erase_index_dir(Dir).

%% used during variable queue purge when there are no pending acks

-spec reset_state(qistate()) -> qistate().

reset_state(#qistate{ queue_name     = Name,
                      dir            = Dir,
                      on_sync        = OnSyncFun,
                      on_sync_msg    = OnSyncMsgFun,
                      journal_handle = JournalHdl }) ->
    ok = case JournalHdl of
             undefined -> ok;
             _         -> file_handle_cache:close(JournalHdl)
         end,
    ok = erase_index_dir(Dir),
    blank_state_name_dir_funs(Name, Dir, OnSyncFun, OnSyncMsgFun).

-spec init(rabbit_amqqueue:name(),
                 on_sync_fun(), on_sync_fun()) -> qistate().

init(#resource{ virtual_host = VHost } = Name, OnSyncFun, OnSyncMsgFun) ->
    #{segment_entry_count := SegmentEntryCount} = rabbit_vhost:read_config(VHost),
    put(segment_entry_count, SegmentEntryCount),
    VHostDir = rabbit_vhost:msg_store_dir_path(VHost),
    State = #qistate { dir = Dir } = blank_state(VHostDir, Name),
    false = rabbit_file:is_file(Dir), %% is_file == is file or dir
    State#qistate{on_sync     = OnSyncFun,
                  on_sync_msg = OnSyncMsgFun}.

init_args(#qistate{ queue_name  = QueueName,
                    on_sync     = OnSyncFun,
                    on_sync_msg = OnSyncMsgFun }) ->
    {QueueName, OnSyncFun, OnSyncMsgFun}.

init_for_conversion(#resource{ virtual_host = VHost } = Name, OnSyncFun, OnSyncMsgFun) ->
    #{segment_entry_count := SegmentEntryCount} = rabbit_vhost:read_config(VHost),
    put(segment_entry_count, SegmentEntryCount),
    VHostDir = rabbit_vhost:msg_store_dir_path(VHost),
    State = blank_state(VHostDir, Name),
    State#qistate{on_sync     = OnSyncFun,
                  on_sync_msg = OnSyncMsgFun}.

-spec recover(rabbit_amqqueue:name(), shutdown_terms(), boolean(),
                    contains_predicate(),
                    on_sync_fun(), on_sync_fun(),
                    main | convert) ->
                        {'undefined' | non_neg_integer(),
                         'undefined' | non_neg_integer(), qistate()}.

recover(#resource{ virtual_host = VHost } = Name, Terms, MsgStoreRecovered,
        ContainsCheckFun, OnSyncFun, OnSyncMsgFun, Context) ->
    #{segment_entry_count := SegmentEntryCount} = rabbit_vhost:read_config(VHost),
    put(segment_entry_count, SegmentEntryCount),
    VHostDir = rabbit_vhost:msg_store_dir_path(VHost),
    State = blank_state(VHostDir, Name),
    State1 = State #qistate{on_sync     = OnSyncFun,
                            on_sync_msg = OnSyncMsgFun},
    CleanShutdown = Terms /= non_clean_shutdown,
    case CleanShutdown andalso MsgStoreRecovered of
        true  -> case proplists:get_value(segments, Terms, non_clean_shutdown) of
                     non_clean_shutdown -> init_dirty(false, ContainsCheckFun, State1, Context);
                     RecoveredCounts    -> init_clean(RecoveredCounts, State1)
                 end;
        false -> init_dirty(CleanShutdown, ContainsCheckFun, State1, Context)
    end.

-spec terminate(rabbit_types:vhost(), [any()], qistate()) -> qistate().

terminate(VHost, Terms, State = #qistate { dir = Dir }) ->
    {SegmentCounts, State1} = terminate(State),
    _ = rabbit_recovery_terms:store(VHost, filename:basename(Dir),
                                    [{segments, SegmentCounts} | Terms]),
    State1.

-spec delete_and_terminate(qistate()) -> qistate().

delete_and_terminate(State) ->
    {_SegmentCounts, State1 = #qistate { dir = Dir }} = terminate(State),
    ok = rabbit_file:recursive_delete([Dir]),
    State1.

-spec info(qistate()) -> [].

%% No info is implemented for v1 at this time.
info(_) -> [].

pre_publish(MsgOrId, SeqId, MsgProps, IsPersistent, IsDelivered, JournalSizeHint,
            State = #qistate{pre_publish_cache = PPC,
                             delivered_cache   = DC}) ->
    State1 = maybe_needs_confirming(MsgProps, MsgOrId, State),

    {Bin, MsgBin} = create_pub_record_body(MsgOrId, MsgProps),

    PPC1 =
        [[<<(case IsPersistent of
                true  -> ?PUB_PERSIST_JPREFIX;
                false -> ?PUB_TRANS_JPREFIX
            end):?JPREFIX_BITS,
           SeqId:?SEQ_BITS, Bin/binary,
           (size(MsgBin)):?EMBEDDED_SIZE_BITS>>, MsgBin] | PPC],

    DC1 =
        case IsDelivered of
            true ->
                [SeqId | DC];
            false ->
                DC
        end,

    State2 = add_to_journal(SeqId, {IsPersistent, Bin, MsgBin}, State1),
    maybe_flush_pre_publish_cache(
                     JournalSizeHint,
                     State2#qistate{pre_publish_cache = PPC1,
                                    delivered_cache   = DC1}).

%% pre_publish_cache is the entry with most elements when compared to
%% delivered_cache so we only check the former in the guard.
maybe_flush_pre_publish_cache(JournalSizeHint,
                              #qistate{pre_publish_cache = PPC} = State) ->
    case length(PPC) >= segment_entry_count() of
        true -> flush_pre_publish_cache(JournalSizeHint, State);
        false -> State
    end.

flush_pre_publish_cache(JournalSizeHint, State) ->
    State1 = flush_pre_publish_cache(State),
    State2 = flush_delivered_cache(State1),
    maybe_flush_journal(JournalSizeHint, State2).

flush_pre_publish_cache(#qistate{pre_publish_cache = []} = State) ->
    State;
flush_pre_publish_cache(State = #qistate{pre_publish_cache = PPC}) ->
    {JournalHdl, State1} = get_journal_handle(State),
    ok = file_handle_cache:append(JournalHdl, lists:reverse(PPC)),
    State1#qistate{pre_publish_cache = []}.

flush_delivered_cache(#qistate{delivered_cache = []} = State) ->
    State;
flush_delivered_cache(State = #qistate{delivered_cache = DC}) ->
    State1 = deliver(lists:reverse(DC), State),
    State1#qistate{delivered_cache = []}.

publish(MsgOrId, SeqId, _Location, MsgProps, IsPersistent, JournalSizeHint, State) ->
    {JournalHdl, State1} =
        get_journal_handle(
          maybe_needs_confirming(MsgProps, MsgOrId, State)),
    {Bin, MsgBin} = create_pub_record_body(MsgOrId, MsgProps),
    ok = file_handle_cache:append(
           JournalHdl, [<<(case IsPersistent of
                               true  -> ?PUB_PERSIST_JPREFIX;
                               false -> ?PUB_TRANS_JPREFIX
                           end):?JPREFIX_BITS,
                          SeqId:?SEQ_BITS, Bin/binary,
                          (size(MsgBin)):?EMBEDDED_SIZE_BITS>>, MsgBin]),
    maybe_flush_journal(
      JournalSizeHint,
      add_to_journal(SeqId, {IsPersistent, Bin, MsgBin}, State1)).

publish(MsgOrId, SeqId, Location, MsgProps, IsPersistent, _, JournalSizeHint, State) ->
    publish(MsgOrId, SeqId, Location, MsgProps, IsPersistent, JournalSizeHint, State).

maybe_needs_confirming(MsgProps, MsgOrId,
        State = #qistate{unconfirmed     = UC,
                         unconfirmed_msg = UCM}) ->
    MsgId = case MsgOrId of
                #basic_message{id = Id} -> Id;
                Id when is_binary(Id)   -> Id
            end,
    ?MSG_ID_BYTES = size(MsgId),
    case {MsgProps#message_properties.needs_confirming, MsgOrId} of
      {true,  MsgId} -> UC1  = sets:add_element(MsgId, UC),
                        State#qistate{unconfirmed     = UC1};
      {true,  _}     -> UCM1 = sets:add_element(MsgId, UCM),
                        State#qistate{unconfirmed_msg = UCM1};
      {false, _}     -> State
    end.

-spec deliver([rabbit_variable_queue:seq_id()], qistate()) -> qistate().

deliver(SeqIds, State) ->
    deliver_or_ack(del, SeqIds, State).

-spec ack([rabbit_variable_queue:seq_id()], qistate()) -> {[], qistate()}.

ack(SeqIds, State) ->
    {[], deliver_or_ack(ack, SeqIds, State)}.

%% This is called when there are outstanding confirms or when the
%% queue is idle and the journal needs syncing (see needs_sync/1).

-spec sync(qistate()) -> qistate().

sync(State = #qistate { journal_handle = undefined }) ->
    State;
sync(State = #qistate { journal_handle = JournalHdl }) ->
    ok = file_handle_cache:sync(JournalHdl),
    notify_sync(State).

-spec needs_sync(qistate()) -> 'confirms' | 'other' | 'false'.

needs_sync(#qistate{journal_handle = undefined}) ->
    false;
needs_sync(#qistate{journal_handle  = JournalHdl,
                    unconfirmed     = UC,
                    unconfirmed_msg = UCM}) ->
    case sets:is_empty(UC) andalso sets:is_empty(UCM) of
        true  -> case file_handle_cache:needs_sync(JournalHdl) of
                     true  -> other;
                     false -> false
                 end;
        false -> confirms
    end.

-spec flush(qistate()) -> qistate().

flush(State = #qistate { dirty_count = 0 }) -> State;
flush(State)                                -> flush_journal(State).

-spec read(rabbit_variable_queue:seq_id(),
           rabbit_variable_queue:seq_id(),
           qistate()) ->
                     {[{rabbit_types:msg_id(), rabbit_variable_queue:seq_id(),
                        rabbit_variable_queue:msg_location(),
                        rabbit_types:message_properties(),
                        boolean()}], qistate()}.

read(StartEnd, StartEnd, State) ->
    {[], State};
read(Start, End, State = #qistate { segments = Segments,
                                    dir = Dir }) when Start =< End ->
    %% Start is inclusive, End is exclusive.
    LowerB = {StartSeg, _StartRelSeq} = seq_id_to_seg_and_rel_seq_id(Start),
    UpperB = {EndSeg,   _EndRelSeq}   = seq_id_to_seg_and_rel_seq_id(End - 1),
    {Messages, Segments1} =
        lists:foldr(fun (Seg, Acc) ->
                            read_bounded_segment(Seg, LowerB, UpperB, Acc, Dir)
                    end, {[], Segments}, lists:seq(StartSeg, EndSeg)),
    {Messages, State #qistate { segments = Segments1 }}.

-spec next_segment_boundary(rabbit_variable_queue:seq_id()) -> rabbit_variable_queue:seq_id().

next_segment_boundary(SeqId) ->
    {Seg, _RelSeq} = seq_id_to_seg_and_rel_seq_id(SeqId),
    reconstruct_seq_id(Seg + 1, 0).

-spec bounds(qistate()) ->
                       {non_neg_integer(), non_neg_integer(), qistate()}.

bounds(State = #qistate { segments = Segments }) ->
    %% This is not particularly efficient, but only gets invoked on
    %% queue initialisation.
    SegNums = lists:sort(segment_nums(Segments)),
    %% Don't bother trying to figure out the lowest seq_id, merely the
    %% seq_id of the start of the lowest segment. That seq_id may not
    %% actually exist, but that's fine. The important thing is that
    %% the segment exists and the seq_id reported is on a segment
    %% boundary.
    %%
    %% We also don't really care about the max seq_id. Just start the
    %% next segment: it makes life much easier.
    %%
    %% SegNums is sorted, ascending.
    {LowSeqId, NextSeqId} =
        case SegNums of
            []         -> {0, 0};
            [MinSeg|_] -> {reconstruct_seq_id(MinSeg, 0),
                           reconstruct_seq_id(1 + lists:last(SegNums), 0)}
        end,
    {LowSeqId, NextSeqId, State}.

-spec start(rabbit_types:vhost(), [rabbit_amqqueue:name()]) -> {[[any()]], {walker(A), A}}.

start(VHost, DurableQueueNames) ->
    {ok, RecoveryTermsPid} = rabbit_recovery_terms:start(VHost),
    rabbit_vhost_sup_sup:save_vhost_recovery_terms(VHost, RecoveryTermsPid),
    {DurableTerms, DurableDirectories} =
        lists:foldl(
          fun(QName, {RecoveryTerms, ValidDirectories}) ->
                  DirName = queue_name_to_dir_name(QName),
                  RecoveryInfo = case rabbit_recovery_terms:read(VHost, DirName) of
                                     {error, _}  -> non_clean_shutdown;
                                     {ok, Terms} -> Terms
                                 end,
                  {[RecoveryInfo | RecoveryTerms],
                   sets:add_element(DirName, ValidDirectories)}
          end, {[], sets:new()}, DurableQueueNames),
    %% Any queue directory we've not been asked to recover is considered garbage
    ToDelete = [filename:join([rabbit_vhost:msg_store_dir_path(VHost), "queues", Dir])
                || Dir <- lists:subtract(all_queue_directory_names(VHost),
                                         sets:to_list(DurableDirectories))],
    rabbit_log:debug("Deleting unknown files/folders: ~p", [ToDelete]),
    _ = rabbit_file:recursive_delete(ToDelete),

    rabbit_recovery_terms:clear(VHost),

    %% The backing queue interface requires that the queue recovery terms
    %% which come back from start/1 are in the same order as DurableQueueNames
    OrderedTerms = lists:reverse(DurableTerms),
    {OrderedTerms, {fun queue_index_walker/1, {start, DurableQueueNames}}}.


stop(VHost) -> rabbit_recovery_terms:stop(VHost).

all_queue_directory_names(VHost) ->
    VHostQueuesPath = filename:join([rabbit_vhost:msg_store_dir_path(VHost), "queues"]),
    case filelib:is_dir(VHostQueuesPath) of
        true  ->
                    {ok, Dirs} = file:list_dir(VHostQueuesPath),
                    Dirs;
        false -> []
    end.

%%----------------------------------------------------------------------------
%% startup and shutdown
%%----------------------------------------------------------------------------

erase_index_dir(Dir) ->
    case rabbit_file:is_dir(Dir) of
        true  -> rabbit_file:recursive_delete([Dir]);
        false -> ok
    end.

blank_state(VHostDir, QueueName) ->
    Dir = queue_dir(VHostDir, QueueName),
    blank_state_name_dir_funs(QueueName,
                         Dir,
                         fun (_) -> ok end,
                         fun (_) -> ok end).

queue_dir(VHostDir, QueueName) ->
    %% Queue directory is
    %% {node_database_dir}/msg_stores/vhosts/{vhost}/queues/{queue}
    QueueDir = queue_name_to_dir_name(QueueName),
    filename:join([VHostDir, "queues", QueueDir]).

queue_name_to_dir_name(#resource { kind = queue,
                                   virtual_host = VHost,
                                   name = QName }) ->
    <<Num:128>> = erlang:md5(<<"queue", VHost/binary, QName/binary>>),
    rabbit_misc:format("~.36B", [Num]).

blank_state_name_dir_funs(Name, Dir, OnSyncFun, OnSyncMsgFun) ->
    {ok, MaxJournal} =
        application:get_env(rabbit, queue_index_max_journal_entries),
    #qistate { dir                 = Dir,
               segments            = segments_new(),
               journal_handle      = undefined,
               dirty_count         = 0,
               max_journal_entries = MaxJournal,
               on_sync             = OnSyncFun,
               on_sync_msg         = OnSyncMsgFun,
               unconfirmed         = sets:new([{version,2}]),
               unconfirmed_msg     = sets:new([{version,2}]),
               pre_publish_cache   = [],
               delivered_cache     = [],
               queue_name          = Name }.

init_clean(RecoveredCounts, State) ->
    %% Load the journal. Since this is a clean recovery this (almost)
    %% gets us back to where we were on shutdown.
    State1 = #qistate { dir = Dir, segments = Segments } = load_journal(State),
    %% The journal loading only creates records for segments touched
    %% by the journal, and the counts are based on the journal entries
    %% only. We need *complete* counts for *all* segments. By an
    %% amazing coincidence we stored that information on shutdown.
    Segments1 =
        lists:foldl(
          fun ({Seg, UnackedCount}, SegmentsN) ->
                  Segment = segment_find_or_new(Seg, Dir, SegmentsN),
                  segment_store(Segment #segment { unacked = UnackedCount },
                                SegmentsN)
          end, Segments, RecoveredCounts),
    %% the counts above include transient messages, which would be the
    %% wrong thing to return
    {undefined, undefined, State1 # qistate { segments = Segments1 }}.

-define(RECOVER_COUNT, 1).
-define(RECOVER_BYTES, 2).
-define(RECOVER_COUNTER_SIZE, 2).

init_dirty(CleanShutdown, ContainsCheckFun, State, Context) ->
    %% Recover the journal completely. This will also load segments
    %% which have entries in the journal and remove duplicates. The
    %% counts will correctly reflect the combination of the segment
    %% and the journal.
    State1 = #qistate { dir = Dir, segments = Segments } =
        recover_journal(State),
    {Segments1, Count, Bytes, DirtyCount} =
        %% Load each segment in turn and filter out messages that are
        %% not in the msg_store, by adding acks to the journal. These
        %% acks only go to the RAM journal as it doesn't matter if we
        %% lose them. Also mark delivered if not clean shutdown. Also
        %% find the number of unacked messages. Also accumulate the
        %% dirty count here, so we can call maybe_flush_journal below
        %% and avoid unnecessary file system operations.
        lists:foldl(
          fun (Seg, {Segments2, CountAcc, BytesAcc, DirtyCount}) ->
                  {{Segment = #segment { unacked = UnackedCount }, Dirty},
                   UnackedBytes} =
                      recover_segment(ContainsCheckFun, CleanShutdown,
                                      segment_find_or_new(Seg, Dir, Segments2),
                                      State1#qistate.max_journal_entries),
                  {segment_store(Segment, Segments2),
                   CountAcc + UnackedCount,
                   BytesAcc + UnackedBytes, DirtyCount + Dirty}
          end, {Segments, 0, 0, 0}, all_segment_nums(State1)),
    %% We force flush the journal to avoid getting into a bad state
    %% when the node gets shut down immediately after init. It takes
    %% a few restarts for the problem to materialize itself, with
    %% at least one message published, followed by the process crashing,
    %% followed by a recovery that is dirty due to term mismatch in the
    %% message store, followed by two clean recoveries. This last
    %% recovery fails with a crash.
    State2 = flush_journal(State1 #qistate { segments = Segments1,
                                             dirty_count = DirtyCount }),
    case Context of
        convert ->
            {Count, Bytes, State2};
        main ->
            %% We try to see if there are segment files from the v2 index.
            case rabbit_file:wildcard(".*\\.qi", Dir) of
                %% We are recovering a dirty queue that was using the v2 index or in
                %% the process of converting from v2 to v1.
                [_|_] ->
                    #resource{virtual_host = VHost, name = QName} = State2#qistate.queue_name,
                    rabbit_log:info("Queue ~ts in vhost ~ts recovered ~b total messages before resuming convert",
                                    [QName, VHost, Count]),
                    CountersRef = counters:new(?RECOVER_COUNTER_SIZE, []),
                    State3 = recover_index_v2_dirty(State2, ContainsCheckFun, CountersRef),
                    {Count + counters:get(CountersRef, ?RECOVER_COUNT),
                     Bytes + counters:get(CountersRef, ?RECOVER_BYTES),
                     State3};
                %% Otherwise keep default values.
                [] ->
                    {Count, Bytes, State2}
            end
    end.

recover_index_v2_dirty(State0 = #qistate { queue_name = Name,
                                           on_sync = OnSyncFun,
                                           on_sync_msg = OnSyncMsgFun },
                       ContainsCheckFun, CountersRef) ->
    #resource{virtual_host = VHost, name = QName} = Name,
    rabbit_log:info("Converting queue ~ts in vhost ~ts from v2 to v1 after unclean shutdown", [QName, VHost]),
    %% We cannot use the counts/bytes because some messages may be in both
    %% the v1 and v2 indexes after a crash.
    {_, _, V2State} = rabbit_classic_queue_index_v2:recover(Name, non_clean_shutdown, true,
                                                            ContainsCheckFun, OnSyncFun, OnSyncMsgFun,
                                                            convert),
    State = recover_index_v2_common(State0, V2State, CountersRef),
    rabbit_log:info("Queue ~ts in vhost ~ts converted ~b total messages from v2 to v1",
                    [QName, VHost, counters:get(CountersRef, ?RECOVER_COUNT)]),
    State.

%% At this point all messages are persistent because transient messages
%% were dropped during the v2 index recovery.
recover_index_v2_common(State0 = #qistate { queue_name = Name, dir = Dir },
                        V2State, CountersRef) ->
    %% Use a temporary per-queue store state to read embedded messages.
    StoreState0 = rabbit_classic_queue_store_v2:init(Name),
    %% Go through the v2 index and publish messages to v1 index.
    {LoSeqId, HiSeqId, _} = rabbit_classic_queue_index_v2:bounds(V2State),
    %% When resuming after a crash we need to double check the messages that are both
    %% in the v1 and v2 index (effectively the messages below the upper bound of the
    %% v1 index that are about to be written to it).
    {_, V1HiSeqId, _} = bounds(State0),
    SkipFun = fun
        (SeqId, FunState0) when SeqId < V1HiSeqId ->
            case read(SeqId, SeqId + 1, FunState0) of
                %% Message already exists, skip.
                {[_], FunState} ->
                    {skip, FunState};
                %% Message doesn't exist, write.
                {[], FunState} ->
                    {write, FunState}
            end;
        %% Message is out of bounds of the v1 index.
        (_, FunState) ->
            {write, FunState}
    end,
    %% We use a common function also used with conversion on policy change.
    {State1, _StoreState} = rabbit_variable_queue:convert_from_v2_to_v1_loop(Name, State0, V2State, StoreState0,
                                                                            {CountersRef, ?RECOVER_COUNT, ?RECOVER_BYTES},
                                                                            LoSeqId, HiSeqId, SkipFun),
    %% Delete any remaining v2 index files.
    OldFiles = rabbit_file:wildcard(".*\\.qi", Dir)
            ++ rabbit_file:wildcard(".*\\.qs", Dir),
    _ = [rabbit_file:delete(filename:join(Dir, F)) || F <- OldFiles],
    %% Ensure that everything in the v1 index is written to disk.
    State = flush(State1),
    %% Clean up all the garbage that we have surely been creating.
    garbage_collect(),
    State.

terminate(State = #qistate { journal_handle = JournalHdl,
                             segments = Segments }) ->
    ok = case JournalHdl of
             undefined -> ok;
             _         -> file_handle_cache:close(JournalHdl)
         end,
    SegmentCounts =
        segment_fold(
          fun (#segment { num = Seg, unacked = UnackedCount }, Acc) ->
                  [{Seg, UnackedCount} | Acc]
          end, [], Segments),
    {SegmentCounts, State #qistate { journal_handle = undefined,
                                     segments = undefined }}.

recover_segment(ContainsCheckFun, CleanShutdown,
                Segment = #segment { journal_entries = JEntries }, MaxJournal) ->
    {SegEntries, UnackedCount} = load_segment(false, Segment),
    {SegEntries1, UnackedCountDelta} =
        segment_plus_journal(SegEntries, JEntries),
    array:sparse_foldl(
      fun (RelSeq, {{IsPersistent, Bin, MsgBin}, Del, no_ack},
           {SegmentAndDirtyCount, Bytes}) ->
              {MsgOrId, MsgProps} = parse_pub_record_body(Bin, MsgBin),
              {recover_message(ContainsCheckFun(MsgOrId), CleanShutdown,
                               Del, RelSeq, SegmentAndDirtyCount, MaxJournal),
               %% @todo If the message is dropped we shouldn't add the size?
               Bytes + case IsPersistent of
                           true  -> MsgProps#message_properties.size;
                           false -> 0
                       end}
      end,
      {{Segment #segment { unacked = UnackedCount + UnackedCountDelta }, 0}, 0},
      SegEntries1).

recover_message( true,  true,   _Del, _RelSeq, SegmentAndDirtyCount, _MaxJournal) ->
    SegmentAndDirtyCount;
recover_message( true, false,    del, _RelSeq, SegmentAndDirtyCount, _MaxJournal) ->
    SegmentAndDirtyCount;
recover_message( true, false, no_del,  RelSeq, {Segment, _DirtyCount}, MaxJournal) ->
    %% force to flush the segment
    {add_to_journal(RelSeq, del, Segment), MaxJournal + 1};
recover_message(false,     _,    del,  RelSeq, {Segment, DirtyCount}, _MaxJournal) ->
    {add_to_journal(RelSeq, ack, Segment), DirtyCount + 1};
recover_message(false,     _, no_del,  RelSeq, {Segment, DirtyCount}, _MaxJournal) ->
    {add_to_journal(RelSeq, ack,
                    add_to_journal(RelSeq, del, Segment)),
     DirtyCount + 2}.

%%----------------------------------------------------------------------------
%% msg store startup delta function
%%----------------------------------------------------------------------------

queue_index_walker({start, DurableQueues}) when is_list(DurableQueues) ->
    {ok, Gatherer} = gatherer:start_link(),
    [begin
         ok = gatherer:fork(Gatherer),
         ok = worker_pool:submit_async(
                fun () -> link(Gatherer),
                          ok = queue_index_walker_reader(QueueName, Gatherer),
                          unlink(Gatherer),
                          ok
                end)
     end || QueueName <- DurableQueues],
    queue_index_walker({next, Gatherer});

queue_index_walker({next, Gatherer}) when is_pid(Gatherer) ->
    case gatherer:out(Gatherer) of
        empty ->
            ok = gatherer:stop(Gatherer),
            finished;
        {value, {MsgId, Count}} ->
            {MsgId, Count, {next, Gatherer}}
    end.

queue_index_walker_reader(QueueName, Gatherer) ->
    ok = scan_queue_segments(
           fun (_SeqId, MsgId, _MsgProps, true, _IsDelivered, no_ack, ok)
                 when is_binary(MsgId) ->
                   gatherer:sync_in(Gatherer, {MsgId, 1});
               (_SeqId, _MsgId, _MsgProps, _IsPersistent, _IsDelivered,
                _IsAcked, Acc) ->
                   Acc
           end, ok, QueueName),
    ok = gatherer:finish(Gatherer).

scan_queue_segments(Fun, Acc, #resource{ virtual_host = VHost } = QueueName) ->
    %% Set the segment_entry_count for this worker process.
    #{segment_entry_count := SegmentEntryCount} = rabbit_vhost:read_config(VHost),
    put(segment_entry_count, SegmentEntryCount),
    VHostDir = rabbit_vhost:msg_store_dir_path(VHost),
    scan_queue_segments(Fun, Acc, VHostDir, QueueName).

scan_queue_segments(Fun, Acc, VHostDir, QueueName) ->
    State = #qistate { segments = Segments, dir = Dir } =
        recover_journal(blank_state(VHostDir, QueueName)),
    Result = lists:foldr(
      fun (Seg, AccN) ->
              segment_entries_foldr(
                fun (RelSeq, {{MsgOrId, MsgProps, IsPersistent},
                              IsDelivered, IsAcked}, AccM) ->
                        Fun(reconstruct_seq_id(Seg, RelSeq), MsgOrId, MsgProps,
                            IsPersistent, IsDelivered, IsAcked, AccM)
                end, AccN, segment_find_or_new(Seg, Dir, Segments))
      end, Acc, all_segment_nums(State)),
    {_SegmentCounts, _State} = terminate(State),
    Result.

%%----------------------------------------------------------------------------
%% expiry/binary manipulation
%%----------------------------------------------------------------------------

create_pub_record_body(MsgOrId, #message_properties { expiry = Expiry,
                                                      size   = Size }) ->
    ExpiryBin = expiry_to_binary(Expiry),
    case MsgOrId of
        MsgId when is_binary(MsgId) ->
            {<<MsgId/binary, ExpiryBin/binary, Size:?SIZE_BITS>>, <<>>};
        #basic_message{id = MsgId} ->
            MsgBin = term_to_binary(MsgOrId),
            {<<MsgId/binary, ExpiryBin/binary, Size:?SIZE_BITS>>, MsgBin}
    end.

expiry_to_binary(undefined) -> <<?NO_EXPIRY:?EXPIRY_BITS>>;
expiry_to_binary(Expiry)    -> <<Expiry:?EXPIRY_BITS>>.

parse_pub_record_body(<<MsgIdNum:?MSG_ID_BITS, Expiry:?EXPIRY_BITS,
                        Size:?SIZE_BITS>>, MsgBin) ->
    %% work around for binary data fragmentation. See
    %% rabbit_msg_file:read_next/2
    <<MsgId:?MSG_ID_BYTES/binary>> = <<MsgIdNum:?MSG_ID_BITS>>,
    Props = #message_properties{expiry = case Expiry of
                                             ?NO_EXPIRY -> undefined;
                                             X          -> X
                                         end,
                                size   = Size},
    case MsgBin of
        <<>> -> {MsgId, Props};
        _    -> Msg = #basic_message{id = MsgId} = binary_to_term(MsgBin),
                {Msg, Props}
    end.

%%----------------------------------------------------------------------------
%% journal manipulation
%%----------------------------------------------------------------------------

add_to_journal(SeqId, Action, State = #qistate { dirty_count = DCount,
                                                 segments = Segments,
                                                 dir = Dir }) ->
    {Seg, RelSeq} = seq_id_to_seg_and_rel_seq_id(SeqId),
    Segment = segment_find_or_new(Seg, Dir, Segments),
    Segment1 = add_to_journal(RelSeq, Action, Segment),
    State #qistate { dirty_count = DCount + 1,
                     segments = segment_store(Segment1, Segments) };

add_to_journal(RelSeq, Action,
               Segment = #segment { journal_entries = JEntries,
                                    entries_to_segment = EToSeg,
                                    unacked = UnackedCount }) ->

    {Fun, Entry} = action_to_entry(RelSeq, Action, JEntries),

    {JEntries1, EToSeg1} =
        case Fun of
            set ->
                {array:set(RelSeq, Entry, JEntries),
                 array:set(RelSeq, entry_to_segment(RelSeq, Entry, []),
                           EToSeg)};
            reset ->
                {array:reset(RelSeq, JEntries),
                 array:reset(RelSeq, EToSeg)}
        end,

    Segment #segment {
      journal_entries = JEntries1,
      entries_to_segment = EToSeg1,
      unacked = UnackedCount + case Action of
                                   ?PUB -> +1;
                                   del  ->  0;
                                   ack  -> -1
                               end}.

action_to_entry(RelSeq, Action, JEntries) ->
    case array:get(RelSeq, JEntries) of
        undefined ->
            {set,
             case Action of
                 ?PUB -> {Action, no_del, no_ack};
                 del  -> {no_pub,    del, no_ack};
                 ack  -> {no_pub, no_del,    ack}
             end};
        ({Pub,    no_del, no_ack}) when Action == del ->
            {set, {Pub,    del, no_ack}};
        ({no_pub,    del, no_ack}) when Action == ack ->
            {set, {no_pub, del,    ack}};
        ({?PUB,      del, no_ack}) when Action == ack ->
            {reset, none};
        %% Special case, missing del
        %% See journal_minus_segment1/2
        ({?PUB,   no_del, no_ack}) when Action == ack ->
            {reset, none}
    end.

maybe_flush_journal(State) ->
    maybe_flush_journal(infinity, State).

maybe_flush_journal(Hint, State = #qistate { dirty_count = DCount,
                                             max_journal_entries = MaxJournal })
  when DCount > MaxJournal orelse (Hint =/= infinity andalso DCount > Hint) ->
    flush_journal(State);
maybe_flush_journal(_Hint, State) ->
    State.

flush_journal(State = #qistate { segments = Segments }) ->
    Segments1 =
        segment_fold(
          fun (#segment { unacked = 0, path = Path }, SegmentsN) ->
                  case rabbit_file:is_file(Path) of
                      true  -> ok = rabbit_file:delete(Path);
                      false -> ok
                  end,
                  SegmentsN;
              (#segment {} = Segment, SegmentsN) ->
                  segment_store(append_journal_to_segment(Segment), SegmentsN)
          end, segments_new(), Segments),
    {JournalHdl, State1} =
        get_journal_handle(State #qistate { segments = Segments1 }),
    ok = file_handle_cache:clear(JournalHdl),
    notify_sync(State1 #qistate { dirty_count = 0 }).

append_journal_to_segment(#segment { journal_entries = JEntries,
                                     entries_to_segment = EToSeg,
                                     path = Path } = Segment) ->
    case array:sparse_size(JEntries) of
        0 -> Segment;
        _ ->
            file_handle_cache_stats:update(queue_index_write),

            {ok, Hdl} = file_handle_cache:open_with_absolute_path(
                          Path, ?WRITE_MODE,
                          [{write_buffer, infinity}]),
            %% the file_handle_cache also does a list reverse, so this
            %% might not be required here, but before we were doing a
            %% sparse_foldr, a lists:reverse/1 seems to be the correct
            %% thing to do for now.
            _ = file_handle_cache:append(Hdl, lists:reverse(array:to_list(EToSeg))),
            ok = file_handle_cache:close(Hdl),
            Segment #segment { journal_entries    = array_new(),
                               entries_to_segment = array_new([]) }
    end.

get_journal_handle(State = #qistate { journal_handle = undefined,
                                      dir = Dir,
                                      queue_name = Name }) ->
    Path = filename:join(Dir, ?JOURNAL_FILENAME),
    ok = rabbit_file:ensure_dir(Path),
    ok = ensure_queue_name_stub_file(Dir, Name),
    {ok, Hdl} = file_handle_cache:open_with_absolute_path(
                  Path, ?WRITE_MODE, [{write_buffer, infinity}]),
    {Hdl, State #qistate { journal_handle = Hdl }};
get_journal_handle(State = #qistate { journal_handle = Hdl }) ->
    {Hdl, State}.

%% Loading Journal. This isn't idempotent and will mess up the counts
%% if you call it more than once on the same state. Assumes the counts
%% are 0 to start with.
load_journal(State = #qistate { dir = Dir }) ->
    Path = filename:join(Dir, ?JOURNAL_FILENAME),
    case rabbit_file:is_file(Path) of
        true  -> {JournalHdl, State1} = get_journal_handle(State),
                 Size = rabbit_file:file_size(Path),
                 {ok, 0} = file_handle_cache:position(JournalHdl, 0),
                 {ok, JournalBin} = file_handle_cache:read(JournalHdl, Size),
                 parse_journal_entries(JournalBin, State1);
        false -> State
    end.

%% ditto
recover_journal(State) ->
    State1 = #qistate { segments = Segments } = load_journal(State),
    Segments1 =
        segment_map(
          fun (Segment = #segment { journal_entries = JEntries,
                                    entries_to_segment = EToSeg,
                                    unacked = UnackedCountInJournal }) ->
                  %% We want to keep ack'd entries in so that we can
                  %% remove them if duplicates are in the journal. The
                  %% counts here are purely from the segment itself.
                  {SegEntries, UnackedCountInSeg} = load_segment(true, Segment),
                  {JEntries1, EToSeg1, UnackedCountDuplicates} =
                      journal_minus_segment(JEntries, EToSeg, SegEntries),
                  Segment #segment { journal_entries = JEntries1,
                                     entries_to_segment = EToSeg1,
                                     unacked = (UnackedCountInJournal +
                                                    UnackedCountInSeg -
                                                    UnackedCountDuplicates) }
          end, Segments),
    State1 #qistate { segments = Segments1 }.

parse_journal_entries(<<?DEL_JPREFIX:?JPREFIX_BITS, SeqId:?SEQ_BITS,
                        Rest/binary>>, State) ->
    parse_journal_entries(Rest, add_to_journal(SeqId, del, State));

parse_journal_entries(<<?ACK_JPREFIX:?JPREFIX_BITS, SeqId:?SEQ_BITS,
                        Rest/binary>>, State) ->
    parse_journal_entries(Rest, add_to_journal(SeqId, ack, State));
parse_journal_entries(<<0:?JPREFIX_BITS, 0:?SEQ_BITS,
                        0:?PUB_RECORD_SIZE_BYTES/unit:8, _/binary>>, State) ->
    %% Journal entry composed only of zeroes was probably
    %% produced during a dirty shutdown so stop reading
    State;
parse_journal_entries(<<Prefix:?JPREFIX_BITS, SeqId:?SEQ_BITS,
                        Bin:?PUB_RECORD_BODY_BYTES/binary,
                        MsgSize:?EMBEDDED_SIZE_BITS, MsgBin:MsgSize/binary,
                        Rest/binary>>, State) ->
    IsPersistent = case Prefix of
                       ?PUB_PERSIST_JPREFIX -> true;
                       ?PUB_TRANS_JPREFIX   -> false
                   end,
    parse_journal_entries(
      Rest, add_to_journal(SeqId, {IsPersistent, Bin, MsgBin}, State));
parse_journal_entries(_ErrOrEoF, State) ->
    State.

deliver_or_ack(_Kind, [], State) ->
    State;
deliver_or_ack(Kind, SeqIds, State) ->
    JPrefix = case Kind of ack -> ?ACK_JPREFIX; del -> ?DEL_JPREFIX end,
    {JournalHdl, State1} = get_journal_handle(State),
    ok = file_handle_cache:append(
           JournalHdl,
           [<<JPrefix:?JPREFIX_BITS, SeqId:?SEQ_BITS>> || SeqId <- SeqIds]),
    maybe_flush_journal(lists:foldl(fun (SeqId, StateN) ->
                                            add_to_journal(SeqId, Kind, StateN)
                                    end, State1, SeqIds)).

notify_sync(State = #qistate{unconfirmed     = UC,
                             unconfirmed_msg = UCM,
                             on_sync         = OnSyncFun,
                             on_sync_msg     = OnSyncMsgFun}) ->
    State1 = case sets:is_empty(UC) of
                 true  -> State;
                 false -> OnSyncFun(UC),
                          State#qistate{unconfirmed = sets:new([{version,2}])}
             end,
    case sets:is_empty(UCM) of
        true  -> State1;
        false -> OnSyncMsgFun(UCM),
                 State1#qistate{unconfirmed_msg = sets:new([{version,2}])}
    end.

%%----------------------------------------------------------------------------
%% segment manipulation
%%----------------------------------------------------------------------------

seq_id_to_seg_and_rel_seq_id(SeqId) ->
    SegmentEntryCount = segment_entry_count(),
    { SeqId div SegmentEntryCount, SeqId rem SegmentEntryCount }.

reconstruct_seq_id(Seg, RelSeq) ->
    (Seg * segment_entry_count()) + RelSeq.

all_segment_nums(#qistate { dir = Dir, segments = Segments }) ->
    lists:sort(
      sets:to_list(
        lists:foldl(
          fun (SegName, Set) ->
                  sets:add_element(
                    list_to_integer(
                      lists:takewhile(fun (C) -> $0 =< C andalso C =< $9 end,
                                      SegName)), Set)
          end, sets:from_list(segment_nums(Segments)),
          rabbit_file:wildcard(".*\\" ++ ?SEGMENT_EXTENSION, Dir)))).

segment_find_or_new(Seg, Dir, Segments) ->
    case segment_find(Seg, Segments) of
        {ok, Segment} -> Segment;
        error         -> SegName = integer_to_list(Seg)  ++ ?SEGMENT_EXTENSION,
                         Path = filename:join(Dir, SegName),
                         #segment { num                = Seg,
                                    path               = Path,
                                    journal_entries    = array_new(),
                                    entries_to_segment = array_new([]),
                                    unacked            = 0 }
    end.

segment_find(Seg, {_Segments, [Segment = #segment { num = Seg } |_]}) ->
    {ok, Segment}; %% 1 or (2, matches head)
segment_find(Seg, {_Segments, [_, Segment = #segment { num = Seg }]}) ->
    {ok, Segment}; %% 2, matches tail
segment_find(Seg, {Segments, _}) -> %% no match
    maps:find(Seg, Segments).

segment_store(Segment = #segment { num = Seg }, %% 1 or (2, matches head)
              {Segments, [#segment { num = Seg } | Tail]}) ->
    {Segments, [Segment | Tail]};
segment_store(Segment = #segment { num = Seg }, %% 2, matches tail
              {Segments, [SegmentA, #segment { num = Seg }]}) ->
    {Segments, [Segment, SegmentA]};
segment_store(Segment = #segment { num = Seg }, {Segments, []}) ->
    {maps:remove(Seg, Segments), [Segment]};
segment_store(Segment = #segment { num = Seg }, {Segments, [SegmentA]}) ->
    {maps:remove(Seg, Segments), [Segment, SegmentA]};
segment_store(Segment = #segment { num = Seg },
              {Segments, [SegmentA, SegmentB]}) ->
    {maps:put(SegmentB#segment.num, SegmentB, maps:remove(Seg, Segments)),
     [Segment, SegmentA]}.

segment_fold(Fun, Acc, {Segments, CachedSegments}) ->
    maps:fold(fun (_Seg, Segment, Acc1) -> Fun(Segment, Acc1) end,
              lists:foldl(Fun, Acc, CachedSegments), Segments).

segment_map(Fun, {Segments, CachedSegments}) ->
    {maps:map(fun (_Seg, Segment) -> Fun(Segment) end, Segments),
     lists:map(Fun, CachedSegments)}.

segment_nums({Segments, CachedSegments}) ->
    lists:map(fun (#segment { num = Num }) -> Num end, CachedSegments) ++
        maps:keys(Segments).

segments_new() ->
    {#{}, []}.

entry_to_segment(_RelSeq, {?PUB, del, ack}, Initial) ->
    Initial;
entry_to_segment(RelSeq, {Pub, Del, Ack}, Initial) ->
    %% NB: we are assembling the segment in reverse order here, so
    %% del/ack comes first.
    Buf1 = case {Del, Ack} of
               {no_del, no_ack} ->
                   Initial;
               _ ->
                   Binary = <<?REL_SEQ_ONLY_PREFIX:?REL_SEQ_ONLY_PREFIX_BITS,
                              RelSeq:?REL_SEQ_BITS>>,
                   case {Del, Ack} of
                       {del, ack} -> [[Binary, Binary] | Initial];
                       _          -> [Binary | Initial]
                   end
           end,
    case Pub of
        no_pub ->
            Buf1;
        {IsPersistent, Bin, MsgBin} ->
            [[<<?PUB_PREFIX:?PUB_PREFIX_BITS,
                (bool_to_int(IsPersistent)):1,
                RelSeq:?REL_SEQ_BITS, Bin/binary,
                (size(MsgBin)):?EMBEDDED_SIZE_BITS>>, MsgBin] | Buf1]
    end.

read_bounded_segment(Seg, {StartSeg, StartRelSeq}, {EndSeg, EndRelSeq},
                     {Messages, Segments}, Dir) ->
    Segment = segment_find_or_new(Seg, Dir, Segments),
    {segment_entries_foldr(
       fun (RelSeq, {{MsgOrId, MsgProps, IsPersistent}, _IsDelivered, no_ack},
            Acc)
             when (Seg > StartSeg orelse StartRelSeq =< RelSeq) andalso
                  (Seg < EndSeg   orelse EndRelSeq   >= RelSeq) ->
               MsgLocation = case is_tuple(MsgOrId) of
                   true -> rabbit_queue_index;
                   false -> rabbit_msg_store
               end,
               [{MsgOrId, reconstruct_seq_id(StartSeg, RelSeq), MsgLocation, MsgProps,
                 IsPersistent} | Acc];
           (_RelSeq, _Value, Acc) ->
               Acc
       end, Messages, Segment),
     segment_store(Segment, Segments)}.

segment_entries_foldr(Fun, Init,
                      Segment = #segment { journal_entries = JEntries }) ->
    {SegEntries, _UnackedCount} = load_segment(false, Segment),
    {SegEntries1, _UnackedCountD} = segment_plus_journal(SegEntries, JEntries),
    array:sparse_foldr(
      fun (RelSeq, {{IsPersistent, Bin, MsgBin}, Del, Ack}, Acc) ->
              {MsgOrId, MsgProps} = parse_pub_record_body(Bin, MsgBin),
              Fun(RelSeq, {{MsgOrId, MsgProps, IsPersistent}, Del, Ack}, Acc)
      end, Init, SegEntries1).

%% Loading segments
%%
%% Does not do any combining with the journal at all.
load_segment(KeepAcked, #segment { path = Path }) ->
    Empty = {array_new(), 0},
    case rabbit_file:is_file(Path) of
        false -> Empty;
        true  -> Size = rabbit_file:file_size(Path),
                 file_handle_cache_stats:update(queue_index_read),
                 {ok, Hdl} = file_handle_cache:open_with_absolute_path(
                               Path, ?READ_MODE, []),
                 {ok, 0} = file_handle_cache:position(Hdl, bof),
                 {ok, SegBin} = file_handle_cache:read(Hdl, Size),
                 ok = file_handle_cache:close(Hdl),
                 %% We check if the file is full of 0s. I do not know why this can happen
                 %% but this happens AT LEAST during v2->v1 conversion when resuming after
                 %% a crash has happened. Since the file is invalid, we delete it and
                 %% return no entries instead of just crashing (just like if the file
                 %% was missing above). We also log some information.
                 case SegBin of
                     <<0:Size/unit:8>> ->
                         rabbit_log:warning("Deleting invalid v1 segment file ~ts (file only contains NUL bytes)",
                                            [Path]),
                         _ = rabbit_file:delete(Path),
                         Empty;
                     _ ->
                         Res = parse_segment_entries(SegBin, KeepAcked, Empty),
                         Res
                 end
    end.

parse_segment_entries(<<?PUB_PREFIX:?PUB_PREFIX_BITS,
                        IsPersistNum:1, RelSeq:?REL_SEQ_BITS, Rest/binary>>,
                      KeepAcked, Acc) ->
    parse_segment_publish_entry(
      Rest, 1 == IsPersistNum, RelSeq, KeepAcked, Acc);
parse_segment_entries(<<?REL_SEQ_ONLY_PREFIX:?REL_SEQ_ONLY_PREFIX_BITS,
                       RelSeq:?REL_SEQ_BITS, Rest/binary>>, KeepAcked, Acc) ->
    parse_segment_entries(
      Rest, KeepAcked, add_segment_relseq_entry(KeepAcked, RelSeq, Acc));
parse_segment_entries(<<>>, _KeepAcked, Acc) ->
    Acc.

parse_segment_publish_entry(<<Bin:?PUB_RECORD_BODY_BYTES/binary,
                              MsgSize:?EMBEDDED_SIZE_BITS,
                              MsgBin:MsgSize/binary, Rest/binary>>,
                            IsPersistent, RelSeq, KeepAcked,
                            {SegEntries, Unacked}) ->
    Obj = {{IsPersistent, Bin, MsgBin}, no_del, no_ack},
    SegEntries1 = array:set(RelSeq, Obj, SegEntries),
    parse_segment_entries(Rest, KeepAcked, {SegEntries1, Unacked + 1});
parse_segment_publish_entry(Rest, _IsPersistent, _RelSeq, KeepAcked, Acc) ->
    parse_segment_entries(Rest, KeepAcked, Acc).

add_segment_relseq_entry(KeepAcked, RelSeq, {SegEntries, Unacked}) ->
    case array:get(RelSeq, SegEntries) of
        {Pub, no_del, no_ack} ->
            {array:set(RelSeq, {Pub, del, no_ack}, SegEntries), Unacked};
        {Pub, del, no_ack} when KeepAcked ->
            {array:set(RelSeq, {Pub, del, ack},    SegEntries), Unacked - 1};
        {_Pub, del, no_ack} ->
            {array:reset(RelSeq,                   SegEntries), Unacked - 1}
    end.

array_new() ->
    array_new(undefined).

array_new(Default) ->
    array:new([{default, Default}, fixed, {size, segment_entry_count()}]).

segment_entry_count() ->
    get(segment_entry_count).

bool_to_int(true ) -> 1;
bool_to_int(false) -> 0.

%%----------------------------------------------------------------------------
%% journal & segment combination
%%----------------------------------------------------------------------------

%% Combine what we have just read from a segment file with what we're
%% holding for that segment in memory. There must be no duplicates.
segment_plus_journal(SegEntries, JEntries) ->
    array:sparse_foldl(
      fun (RelSeq, JObj, {SegEntriesOut, AdditionalUnacked}) ->
              SegEntry = array:get(RelSeq, SegEntriesOut),
              {Obj, AdditionalUnackedDelta} =
                  segment_plus_journal1(SegEntry, JObj),
              {case Obj of
                   undefined -> array:reset(RelSeq, SegEntriesOut);
                   _         -> array:set(RelSeq, Obj, SegEntriesOut)
               end,
               AdditionalUnacked + AdditionalUnackedDelta}
      end, {SegEntries, 0}, JEntries).

%% Here, the result is a tuple with the first element containing the
%% item which we may be adding to (for items only in the journal),
%% modifying in (bits in both), or, when returning 'undefined',
%% erasing from (ack in journal, not segment) the segment array. The
%% other element of the tuple is the delta for AdditionalUnacked.
segment_plus_journal1(undefined, {?PUB, no_del, no_ack} = Obj) ->
    {Obj, 1};
segment_plus_journal1(undefined, {?PUB, del, no_ack} = Obj) ->
    {Obj, 1};
segment_plus_journal1(undefined, {?PUB, del, ack}) ->
    {undefined, 0};

segment_plus_journal1({?PUB = Pub, no_del, no_ack}, {no_pub, del, no_ack}) ->
    {{Pub, del, no_ack}, 0};
segment_plus_journal1({?PUB, no_del, no_ack},       {no_pub, del, ack}) ->
    {undefined, -1};
segment_plus_journal1({?PUB, del, no_ack},          {no_pub, no_del, ack}) ->
    {undefined, -1};

%% Special case, missing del
%% See journal_minus_segment1/2
segment_plus_journal1({?PUB, no_del, no_ack},          {no_pub, no_del, ack}) ->
    {undefined, -1}.

%% Remove from the journal entries for a segment, items that are
%% duplicates of entries found in the segment itself. Used on start up
%% to clean up the journal.
%%
%% We need to update the entries_to_segment since they are just a
%% cache of what's on the journal.
journal_minus_segment(JEntries, EToSeg, SegEntries) ->
    array:sparse_foldl(
      fun (RelSeq, JObj, {JEntriesOut, EToSegOut, UnackedRemoved}) ->
              SegEntry = array:get(RelSeq, SegEntries),
              {Obj, UnackedRemovedDelta} =
                  journal_minus_segment1(JObj, SegEntry),
              {JEntriesOut1, EToSegOut1} =
                  case Obj of
                      keep      ->
                          {JEntriesOut, EToSegOut};
                      undefined ->
                          {array:reset(RelSeq, JEntriesOut),
                           array:reset(RelSeq, EToSegOut)};
                      _         ->
                          {array:set(RelSeq, Obj, JEntriesOut),
                           array:set(RelSeq, entry_to_segment(RelSeq, Obj, []),
                                     EToSegOut)}
                  end,
               {JEntriesOut1, EToSegOut1, UnackedRemoved + UnackedRemovedDelta}
      end, {JEntries, EToSeg, 0}, JEntries).

%% Here, the result is a tuple with the first element containing the
%% item we are adding to or modifying in the (initially fresh) journal
%% array. If the item is 'undefined' we leave the journal array
%% alone. The other element of the tuple is the deltas for
%% UnackedRemoved.

%% Both the same. Must be at least the publish
journal_minus_segment1({?PUB, _Del, no_ack} = Obj, Obj) ->
    {undefined, 1};
journal_minus_segment1({?PUB, _Del, ack} = Obj,    Obj) ->
    {undefined, 0};

%% Just publish in journal
journal_minus_segment1({?PUB, no_del, no_ack},     undefined) ->
    {keep, 0};

%% Publish and deliver in journal
journal_minus_segment1({?PUB, del, no_ack},        undefined) ->
    {keep, 0};
journal_minus_segment1({?PUB = Pub, del, no_ack},  {Pub, no_del, no_ack}) ->
    {{no_pub, del, no_ack}, 1};

%% Publish, deliver and ack in journal
journal_minus_segment1({?PUB, del, ack},           undefined) ->
    {keep, 0};
journal_minus_segment1({?PUB = Pub, del, ack},     {Pub, no_del, no_ack}) ->
    {{no_pub, del, ack}, 1};
journal_minus_segment1({?PUB = Pub, del, ack},     {Pub, del, no_ack}) ->
    {{no_pub, no_del, ack}, 1};

%% Just deliver in journal
journal_minus_segment1({no_pub, del, no_ack},      {?PUB, no_del, no_ack}) ->
    {keep, 0};
journal_minus_segment1({no_pub, del, no_ack},      {?PUB, del, no_ack}) ->
    {undefined, 0};

%% Just ack in journal
journal_minus_segment1({no_pub, no_del, ack},      {?PUB, del, no_ack}) ->
    {keep, 0};
journal_minus_segment1({no_pub, no_del, ack},      {?PUB, del, ack}) ->
    {undefined, -1};

%% Just ack in journal, missing del
%% Since 3.10 message delivery is tracked per-queue, not per-message,
%% but to keep queue index v1 format messages are always marked as
%% delivered on publish. But for a message that was published before
%% 3.10 this is not the case and the delivery marker can be missing.
%% As a workaround we add the del marker because if a message is acked
%% it must have been delivered as well.
journal_minus_segment1({no_pub, no_del, ack},         {?PUB, no_del, no_ack}) ->
    {{no_pub, del, ack}, 0};

%% Deliver and ack in journal
journal_minus_segment1({no_pub, del, ack},         {?PUB, no_del, no_ack}) ->
    {keep, 0};
journal_minus_segment1({no_pub, del, ack},         {?PUB, del, no_ack}) ->
    {{no_pub, no_del, ack}, 0};
journal_minus_segment1({no_pub, del, ack},         {?PUB, del, ack}) ->
    {undefined, -1};

%% Missing segment. If flush_journal/1 is interrupted after deleting
%% the segment but before truncating the journal we can get these
%% cases: a delivery and an acknowledgement in the journal, or just an
%% acknowledgement in the journal, but with no segment. In both cases
%% we have really forgotten the message; so ignore what's in the
%% journal.
journal_minus_segment1({no_pub, no_del, ack},      undefined) ->
    {undefined, 0};
journal_minus_segment1({no_pub, del, ack},         undefined) ->
    {undefined, 0}.

%%----------------------------------------------------------------------------
%% Migration functions
%%----------------------------------------------------------------------------

ensure_queue_name_stub_file(Dir, #resource{virtual_host = VHost, name = QName}) ->
    QueueNameFile = filename:join(Dir, ?QUEUE_NAME_STUB_FILE),
    file:write_file(QueueNameFile, <<"VHOST: ", VHost/binary, "\n",
                                     "QUEUE: ", QName/binary, "\n">>).

%% This function is only used when upgrading to the v2 index.
%% We delete the segment file without updating the state.
%% We will drop the state later on so we don't care much
%% about how accurate it is as long as we can read from
%% subsequent segment files.
delete_segment_file_for_seq_id(SeqId, #qistate { segments = Segments }) ->
    {Seg, _} = seq_id_to_seg_and_rel_seq_id(SeqId),
    case segment_find(Seg, Segments) of
        {ok, #segment { path = Path }} ->
            case rabbit_file:delete(Path) of
                ok -> ok;
                %% The file may not exist on disk yet.
                {error, enoent} -> ok
            end;
        error ->
            ok
    end.

delete_journal(#qistate { dir = Dir, journal_handle = JournalHdl }) ->
    %% Close the journal handle if any.
    ok = case JournalHdl of
        undefined -> ok;
        _         -> file_handle_cache:close(JournalHdl)
    end,
    %% Delete the journal file.
    _ = rabbit_file:delete(filename:join(Dir, "journal.jif")),
    ok.
