fl.c

Go to the documentation of this file.

/* -*- C -*- */
/*
 * Copyright (c) 2014-2020 Seagate Technology LLC and/or its Affiliates
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * For any questions about this software or licensing,
 * please email opensource@seagate.com or cortx-questions@seagate.com.
 *
 */

#define M0_TRACE_SUBSYSTEM M0_TRACE_SUBSYS_BE
#include "lib/trace.h"

#include "be/fl.h"

#include "lib/assert.h"         /* M0_PRE */
#include "lib/misc.h"           /* ARRAY_SIZE */
#include "lib/arith.h"          /* min_type */

#include "motr/magic.h"         /* M0_BE_ALLOC_FREE_LINK_MAGIC */

#include "be/tx_credit.h"       /* m0_be_tx_credit */
#include "be/alloc_internal.h"  /* be_alloc_chunk */

M0_BE_LIST_DESCR_DEFINE(fl, "m0_be_fl", static, struct be_alloc_chunk,
                        bac_linkage_free, bac_magic_free,
                        M0_BE_ALLOC_FREE_LINK_MAGIC, M0_BE_ALLOC_FREE_MAGIC);
M0_BE_LIST_DEFINE(fl, static, struct be_alloc_chunk);

static struct m0_be_list *be_fl_list(struct m0_be_fl *fl, unsigned long index)
{
        M0_PRE(index < ARRAY_SIZE(fl->bfl_free));

        return &fl->bfl_free[index].bfs_list;
};

static bool be_fl_list_is_empty(struct m0_be_fl *fl, unsigned long index)
{
        return fl_be_list_is_empty(be_fl_list(fl, index));
}

M0_INTERNAL void m0_be_fl_create(struct m0_be_fl  *fl,
                                 struct m0_be_tx  *tx,
                                 struct m0_be_seg *seg)
{
        int i;

        for (i = 0; i < ARRAY_SIZE(fl->bfl_free); ++i)
                fl_be_list_create(be_fl_list(fl, i), tx);
}

M0_INTERNAL void m0_be_fl_destroy(struct m0_be_fl *fl, struct m0_be_tx *tx)
{
        int i;

        for (i = 0; i < ARRAY_SIZE(fl->bfl_free); ++i)
                fl_be_list_destroy(be_fl_list(fl, i), tx);
}

static unsigned long be_fl_index_round_up(struct m0_be_fl *fl,
                                          m0_bcount_t      size)
{
        return min_type(unsigned long, M0_BE_FL_NR,
                        m0_align(size, M0_BE_FL_STEP) / M0_BE_FL_STEP);
}

static unsigned long
be_fl_index_round_down_chunk(struct m0_be_fl             *fl,
                             const struct be_alloc_chunk *chunk)
{
        return min_type(unsigned long, M0_BE_FL_NR,
                        chunk->bac_size / M0_BE_FL_STEP);
}

M0_INTERNAL bool m0_be_fl__invariant(struct m0_be_fl *fl)
{
        return m0_forall(i, ARRAY_SIZE(fl->bfl_free),
                        m0_be_list_forall(fl, chunk, be_fl_list(fl, i),
                                _0C(be_fl_index_round_down_chunk(fl, chunk) ==
                                    i)));
}

M0_INTERNAL void m0_be_fl_add(struct m0_be_fl       *fl,
                              struct m0_be_tx       *tx,
                              struct be_alloc_chunk *chunk)
{
        unsigned long index = be_fl_index_round_down_chunk(fl, chunk);

        M0_PRE_EX(m0_be_fl__invariant(fl));

        fl_be_tlink_create(chunk, tx);
        fl_be_list_add(be_fl_list(fl, index), tx, chunk);

        M0_POST_EX(m0_be_fl__invariant(fl));
}

M0_INTERNAL void m0_be_fl_del(struct m0_be_fl       *fl,
                              struct m0_be_tx       *tx,
                              struct be_alloc_chunk *chunk)
{
        unsigned long index = be_fl_index_round_down_chunk(fl, chunk);

        M0_PRE_EX(m0_be_fl__invariant(fl));

        fl_be_list_del(be_fl_list(fl, index), tx, chunk);
        fl_be_tlink_destroy(chunk, tx);
        M0_POST_EX(m0_be_fl__invariant(fl));
}

M0_INTERNAL struct be_alloc_chunk *m0_be_fl_pick(struct m0_be_fl *fl,
                                                 m0_bcount_t      size)
{
        struct be_alloc_chunk *chunk;
        struct be_alloc_chunk *iter;
        unsigned long          index;
        struct m0_be_list     *flist;
        int                    i = 0;

        M0_PRE_EX(m0_be_fl__invariant(fl));

        for (index = be_fl_index_round_up(fl, size);
             index < ARRAY_SIZE(fl->bfl_free); ++index) {
                if (!be_fl_list_is_empty(fl, index))
                        break;
        }

        flist = index < ARRAY_SIZE(fl->bfl_free) ? be_fl_list(fl, index) : NULL;
        chunk = flist == NULL ? NULL : fl_be_list_head(flist);
        if (index == M0_BE_FL_NR && chunk != NULL) {
                chunk = NULL;
                m0_be_list_for(fl, flist, iter) {
                        if (iter->bac_size > size &&
                            ergo(chunk != NULL,
                                 chunk->bac_size > iter->bac_size)) {
                                chunk = iter;
                        }
                        ++i;
                        if (i >= M0_BE_FL_PICK_SCAN_LIMIT && chunk != NULL)
                                break;
                } m0_be_list_endfor;
        }

        M0_LOG(M0_DEBUG, "chunk=%p size=%" PRIu64 " bac_size=%" PRIu64 " "
               "index=%lu iterations=%u",
               chunk, size, chunk ? chunk->bac_size : 0, index, i);
        M0_POST(ergo(chunk != NULL, chunk->bac_size >= size));
        return chunk;
}

M0_INTERNAL void m0_be_fl_credit(struct m0_be_fl        *fl,
                                 enum m0_be_fl_op        fl_op,
                                 struct m0_be_tx_credit *accum)
{
        size_t list_nr = ARRAY_SIZE(fl->bfl_free);

        M0_ASSERT_INFO(M0_IN(fl_op, (M0_BFL_CREATE, M0_BFL_DESTROY,
                                     M0_BFL_ADD, M0_BFL_DEL)),
                       "fl_op=%d", fl_op);
        switch (fl_op) {
        case M0_BFL_CREATE:
                fl_be_list_credit(M0_BLO_CREATE, list_nr, accum);
        case M0_BFL_DESTROY:
                fl_be_list_credit(M0_BLO_DESTROY, list_nr, accum);
                break;
        case M0_BFL_ADD:
                fl_be_list_credit(M0_BLO_TLINK_CREATE, 1, accum);
                fl_be_list_credit(M0_BLO_ADD, 1, accum);
                break;
        case M0_BFL_DEL:
                fl_be_list_credit(M0_BLO_DEL, 1, accum);
                fl_be_list_credit(M0_BLO_TLINK_DESTROY, 1, accum);
                break;
        }
}


#undef M0_TRACE_SUBSYSTEM

/*
 *  Local variables:
 *  c-indentation-style: "K&R"
 *  c-basic-offset: 8
 *  tab-width: 8
 *  fill-column: 80
 *  scroll-step: 1
 *  End:
 */
/*
 * vim: tabstop=8 shiftwidth=8 noexpandtab textwidth=80 nowrap
 */