lsn.h

Go to the documentation of this file.

/* -*- mode:C++; c-basic-offset:4 -*-
     Shore-MT -- Multi-threaded port of the SHORE storage manager

                       Copyright (c) 2007-2009
      Data Intensive Applications and Systems Labaratory (DIAS)
               Ecole Polytechnique Federale de Lausanne

                         All Rights Reserved.

   Permission to use, copy, modify and distribute this software and
   its documentation is hereby granted, provided that both the
   copyright notice and this permission notice appear in all copies of
   the software, derivative works or modified versions, and any
   portions thereof, and that both notices appear in supporting
   documentation.

   This code 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. THE AUTHORS
   DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER
   RESULTING FROM THE USE OF THIS SOFTWARE.
*/

/*<std-header orig-src='shore' incl-file-exclusion='SM_S_H'>

 $Id: lsn.h,v 1.5 2010/12/08 17:37:34 nhall Exp $

SHORE -- Scalable Heterogeneous Object REpository

Copyright (c) 1994-99 Computer Sciences Department, University of
                      Wisconsin -- Madison
All Rights Reserved.

Permission to use, copy, modify and distribute this software and its
documentation is hereby granted, provided that both the copyright
notice and this permission notice appear in all copies of the
software, derivative works or modified versions, and any portions
thereof, and that both notices appear in supporting documentation.

THE AUTHORS AND THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY
OF WISCONSIN - MADISON ALLOW FREE USE OF THIS SOFTWARE IN ITS
"AS IS" CONDITION, AND THEY DISCLAIM ANY LIABILITY OF ANY KIND
FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.

This software was developed with support by the Advanced Research
Project Agency, ARPA order number 018 (formerly 8230), monitored by
the U.S. Army Research Laboratory under contract DAAB07-91-C-Q518.
Further funding for this work was provided by DARPA through
Rome Research Laboratory Contract No. F30602-97-2-0247.

*/

#ifndef __LSN_H
#define __LSN_H

#include <iostream>

#include "w_defines.h"
#include "w_base.h"

/* FRJ: Major changes to lsn_t
 * Once the database runs long enough we will run out of
 * partition numbers (only 64k possible).
 * Fortunately, this is a log, so lsn_t don't last forever.
 * Eventually things become durable and the log partition
 * file gets reclaimed (deleted).
 * As long as the first partition is gone before
 * the last one fills, we can simply wrap and change the
 * sense of lsn_t comparisions.
 * as follows:
 *
   Suppose we use unsigned 8 bit partition numbers. If the current
   global lsn has pnum >= 128 (MSB set), any lsn we encounter with
   pnum < 128 (MSB clear) must be older:

   0        1        ...        126        127        128        129        ...         254        255


   On the other hand, if the current global lsn has pnum < 128
   (MSB clear), any lsn we encounter with pnum >= 128 (MSB set)
   must be *older* (ie, the pnum recently wrapped from 255 back to
   0):

   128        129        ...         254        255        0        1        ...        126        127

   The first situation is easy: regular comparisons provide the
   ordering we want; The second is trickier due to the wrapping of
   partition numbers. Fortunately, there's an easy way around the
   problem!  Since the MSB of the pnum is also the MSB of the
   64-bit value holding the lsn, if comparisons interpret the
   64-bit value as signed we get the proper ordering:

   -128        -127        ...        -2        -1        0        1        ...        126        127

   We assume there are enough lsn_t that less than half are in use at
   a time. So, we divide the universe of lsn's into four regions,
   marked by the most significant two bits of the file.

   00+01 - don't care
   01+10 - unsigned comparisons
   10+11 - unsigned comparisons
   11+00 - signed comparisons

   For now, though, we'll just assume overflow doesn't happen ;)
*/

typedef int64_t sm_diskaddr_t;

typedef uint64_t lsndata_t;

const lsndata_t lsndata_null = 0;

const lsndata_t lsndata_max = 0xFFFFFFFFFFFFFFFF;

class lsn_t {
    enum {
        file_hwm = 0xffff
    };
public:
    enum {
        PARTITION_BITS = 16
    };
    enum {
        PARTITION_SHIFT = (64 - PARTITION_BITS)
    };

    static uint64_t mask() {
        static uint64_t const ONE = 1;
        return (ONE << PARTITION_SHIFT) - 1;
    }

    lsn_t() : _data(0) {}

    lsn_t(lsndata_t data) : _data(data) {}

    lsn_t(uint32_t f, sm_diskaddr_t r) :
            _data(from_file(f) | from_rba(r)) {}

    // copy operator
    // lsn_t(const lsn_t & other) : _data(other._data) { }

    lsndata_t data() const {
        return _data;
    }

    void set(lsndata_t data) {
        _data = data;
    }

    bool valid() const {
        // valid is essentially iff file != 0
#if W_DEBUG_LEVEL > 1
        uint64_t  copy_of_data =  _data;
        uint64_t  m =  mask();
        bool first = copy_of_data > m;
        uint64_t  f =
                        to_file(copy_of_data);
        bool second = (f != 0);
        w_assert2(first == second);
#endif
        return (_data > mask());
    }

    uint32_t hi() const {
        return file();
    }

    uint32_t file() const {
        return to_file(_data);
    }

    sm_diskaddr_t lo() const {
        return rba();
    }

    sm_diskaddr_t rba() const {
        return to_rba(_data);
    }

    // WARNING: non-atomic read-modify-write operations!
    void copy_rba(const lsn_t& other) {
        _data = get_file(_data) | get_rba(other._data);
    }

    void set_rba(sm_diskaddr_t& other) {
        _data = get_file(_data) | get_rba(other);
    }

    // WARNING: non-atomic read-modify-write operations!
    lsn_t& advance(int amt) {
        _data += amt;
        return *this;
    }

    lsn_t& operator+=(long delta) {
        return advance(delta);
    }

    lsn_t operator+(long delta) const {
        return lsn_t(*this).advance(delta);
    }

    bool operator>(const lsn_t& l) const {
        return l < *this;
    }

    bool operator<(const lsn_t& l) const {
        return _data < l._data;
    }

    bool operator>=(const lsn_t& l) const {
        return !(*this < l);
    }

    bool operator<=(const lsn_t& l) const {
        return !(*this > l);
    }

    bool operator==(const lsn_t& l) const {
        return _data == l._data;
    }

    bool operator!=(const lsn_t& l) const {
        return !(*this == l);
    }

    std::string str();

    bool is_null() const {
        return _data == 0;
    }

/*
 * This is the SM's idea of on-disk and in-structure
 * things that reflect the size of a "disk".  It
 * is different from fileoff_t because the two are
 * orthogonal.  A system may be constructed that
 * has big addresses, but is only running on
 * a "small file" environment.
 */
    static const int sm_diskaddr_max;

    static const lsn_t null;

    static const lsn_t max;

    friend std::ostream& operator<<(std::ostream&, const lsn_t&);

private:
    lsndata_t _data;

    static uint32_t to_file(uint64_t f) {
        return (uint32_t)(f >> PARTITION_SHIFT);
    }

    static uint64_t get_file(uint64_t data) {
        return data & ~mask();
    }

    static uint64_t from_file(uint32_t data) {
        return ((uint64_t)data) << PARTITION_SHIFT;
    }

    static sm_diskaddr_t to_rba(uint64_t r) {
        return (sm_diskaddr_t)(r & mask());
    }

    static uint64_t get_rba(uint64_t data) {
        return to_rba(data);
    }

    static uint64_t from_rba(sm_diskaddr_t data) {
        return to_rba(data);
    }
};

inline std::ostream& operator<<(std::ostream& o, const lsn_t& l) {
    return o << l.file() << '.' << l.rba();
}

inline std::istream& operator>>(std::istream& i, lsn_t& l) {
    sm_diskaddr_t d;
    char c;
    uint64_t f;
    i >> f >> c >> d;
    l = lsn_t(f, d);
    return i;
}

namespace std {
    template<>
    struct hash<lsn_t> {
        using argument_type = lsn_t;
        using result_type = std::size_t;

        result_type operator()(argument_type const& a) const {
            return std::hash<lsndata_t>()(a.data());
        }
    };
}

#endif // __LSN_H