/*
* libfilo - A File Locking Library
* Alberto Bertogli (albertogli@telpin.com.ar)
*/
#include <sys/types.h> /* for off_t */
#include <pthread.h> /* for mutexes */
#include <semaphore.h> /* for semaphores (duh!) */
#include <stdlib.h> /* for malloc()/free() */
#include <unistd.h> /* for lockf() commands */
#include "libfilo.h"
/* We have two lists for each file lock: one of currently locked portions of
* the file (a portion can have more than one read lock at the same time, but
* only one write lock), and another one with the current waiters for the
* lock.
* FIXME: document this. everything.
*/
#if 0 /* XXX: debug */
#include <stdio.h>
#define printd(...) \
do { \
fprintf(stderr, "%lu ", pthread_self()); \
fprintf(stderr, "%s(): ", __FUNCTION__ ); \
fprintf(stderr, __VA_ARGS__); \
fflush(stderr); \
} while(0)
void printfl(filock_t *fl)
{
struct locked_range *lr;
struct waiter_range *wr;
fprintf(stderr, "Filock show\n");
fprintf(stderr, "Locked:\n");
for (lr = fl->locked; lr != NULL; lr = lr->next) {
fprintf(stderr, "\t%llu -> %llu (%u) (%lu)\n", lr->start,
lr->end, lr->mode, lr->owner);
}
fprintf(stderr, "Waiter:\n");
for (wr = fl->waiters; wr != NULL; wr = wr->next) {
fprintf(stderr, "\t%llu -> %llu (%u) (%lu)\n", wr->start,
wr->end, wr->mode, wr->owner);
}
}
#else
#define printd(...)
#define printfl(X)
#endif
/* Lock/unlock a filock_t */
#define fl_lock(F) do { pthread_mutex_lock(&(F->lock)); } while (0)
#define fl_unlock(F) do { pthread_mutex_unlock(&(F->lock)); } while (0)
/* Initialize a filock_t structure */
int filo_init(filock_t *fl)
{
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL);
pthread_mutex_init(&(fl->lock), &attr);
pthread_mutexattr_destroy(&attr);
fl->locked = NULL;
fl->waiters = NULL;
return 1;
}
/* Frees a filock_t structure */
int filo_free(filock_t *fl)
{
struct locked_range *lr, *nlr;
struct waiter_range *wr, *nwr;
pthread_mutex_destroy(&(fl->lock));
for (lr = fl->locked; lr != NULL; lr = nlr) {
nlr = lr->next;
free(lr);
}
fl->locked = NULL;
for (wr = fl->waiters; wr != NULL; wr = nwr) {
nwr = wr->next;
free(wr);
}
fl->waiters = NULL;
return 1;
}
/* Appends a lock to the filock_t */
static void locked_append(filock_t *fl, off_t start, off_t end, int mode,
pthread_t owner)
{
struct locked_range *lr;
lr = malloc(sizeof(struct locked_range));
lr->start = start;
lr->end = end;
lr->mode = mode;
lr->owner = owner;
if (fl->locked == NULL) {
lr->prev = lr->next = NULL;
fl->locked = lr;
printd("n: %lu-%lu %d %lu\n", start, end, mode, owner);
} else {
lr->prev = NULL;
fl->locked->prev = lr;
lr->next = fl->locked;
fl->locked = lr;
printd("e: %lu-%lu %d %lu\n", start, end, mode, owner);
}
}
/* Checks if this thread owns the given locked range */
static int is_ours(struct locked_range *lr)
{
return !!pthread_equal(lr->owner, pthread_self());
}
/* Checks the given thread owns the given locked range */
static int is_owner(pthread_t owner, struct locked_range *lr)
{
return !!pthread_equal(lr->owner, owner);
}
/* Checks if the range 1 overlaps with the range 2 */
static int range_overlaps(off_t start1, off_t end1, off_t start2, off_t end2)
{
if ( (start1 <= start2 && end1 >= end2) ||
(start1 >= start2 && start1 <= end2) ||
(end1 >= start2 && end1 <= end2) ) {
return 1;
}
return 0;
}
/* Range overlapping check for locked ranges */
static int lr_range_overlaps(struct locked_range *lr, off_t start, off_t end)
{
printd("%lu->%lu ov %lu->%lu: %d\n", lr->start, lr->end, start, end, range_overlaps(lr->start, lr->end, start, end));
return range_overlaps(lr->start, lr->end, start, end);
}
/* Range overlapping check for waiter ranges */
static int wr_range_overlaps(struct waiter_range *wr, off_t start, off_t end)
{
return range_overlaps(wr->start, wr->end, start, end);
}
/* So far we know:
* * there's overlapping between lr and start-end
* * we own lr
* We need to solve the problem by doing:
* * If lr is inside start-end, remove it
* * If start-end is inside lr, do an "exclude" and break lr in two
* * If there's partial overlapping, shrink lr not to step on start-end
*/
static int exclude_range(filock_t *fl, struct locked_range *lr,
off_t start, off_t end)
{
printd("exclude %lu->%lu from %lu->%lu\n", start, end, lr->start, lr->end);
if (lr->start >= start && lr->end <= end) {
/* it's equal or contained inside, tell to remove */
return 0;
} else if (lr->start < start && lr->end <= end) {
/* we're overlapping from the left, shrink it */
printd("shrink end from %lu to %lu\n", lr->end, start - 1);
lr->end = start - 1;
return 1;
} else if (lr->start >= start && lr->end > end) {
/* we're overlapping from the right, shrink it */
printd("shrink start %lu to %lu\n", lr->start, end + 1);
lr->start = end + 1;
return 1;
} else if (lr->start < start && lr->end > end) {
/* start-end is contained inside lr, we need to split lr */
locked_append(fl, lr->start, start - 1, lr->mode,
pthread_self());
locked_append(fl, end + 1, lr->end, lr->mode, pthread_self());
/* tell the caller to remove lr */
return 0;
}
/* we should NEVER enter here, since all the cases should have been
* covered */
return 1;
}
/* Checks if the given thread can lock the given region */
static int can_lock_tid(filock_t *fl, off_t start, off_t end, int mode,
pthread_t owner)
{
struct locked_range *lr;
for (lr = fl->locked; lr != NULL; lr = lr->next) {
/* if we are inside, contained or overlapping somebody else,
* check if:
* * is ours, so we can play with it freely
* * is a write lock and we try to read, can't get it
* * we try to write, can't get it
*/
if (lr_range_overlaps(lr, start, end)) {
if (is_owner(owner, lr)) {
/* this check could be moved before the long
* "if" above, but it's an unlikely case and
* the test could get expensive */
continue;
}
if (mode == FL_WR_MODE || lr->mode == FL_WR_MODE) {
return 0;
}
}
}
printd("can lock it from %lu to %lu as %d\n", start, end, mode);
return 1;
}
/* As can_lock_tid() but gets the owner from the current thread */
static int can_lock(filock_t *fl, off_t start, off_t end, int mode)
{
return can_lock_tid(fl, start, end, mode, pthread_self());
}
/* Lock a given region, assuming that is not free and we're allowed to own it
* (these checks are performed by the caller) */
static int do_lock_tid(filock_t *fl, off_t start, off_t end, int mode,
pthread_t owner)
{
struct locked_range *lr, *next;
for (lr = fl->locked; lr != NULL; lr = next) {
next = lr->next;
if (!is_ours(lr))
continue;
if (!lr_range_overlaps(lr, start, end))
continue;
printd("overlap %lu %lu %d %lu\n", start, end, mode, owner);
if (exclude_range(fl, lr, start, end) == 0) {
printd("rem lr %lu->%lu\n", lr->start, lr->end);
/* we need to remove lr */
if (fl->locked == lr)
fl->locked = lr->next;
if (lr->prev != NULL)
lr->prev->next = lr->next;
if (lr->next != NULL)
lr->next->prev = lr->prev;
free(lr);
}
}
/* now the region is safe to do this */
locked_append(fl, start, end, mode, owner);
return 1;
}
/* Same as do_lock_tid(), but gets the tid from the currently running thread;
* it's a shortcut for a lot of uses */
static int do_lock(filock_t *fl, off_t start, off_t end, int mode)
{
return do_lock_tid(fl, start, end, mode, pthread_self());
}
/* Check if a region is free from locks so we can add the lock right in,
* skipping all the other tests */
static int region_free(filock_t *fl, off_t start, off_t end) {
struct locked_range *lr;
for (lr = fl->locked; lr != NULL; lr = lr->next) {
if (lr_range_overlaps(lr, start, end))
return 0;
}
return 1;
}
/* Tries to get a lock, returns 1 if success or 0 if failure */
int filo_trylock(filock_t *fl, off_t start, off_t len, int mode)
{
int rv = 0;
off_t end = start + len - 1;
if (len <= 0)
return 0;
fl_lock(fl);
/* fast path for the uncontended case */
if (fl->locked == NULL) {
locked_append(fl, start, end, mode, pthread_self());
rv = 1;
} else if (region_free(fl, start, end)) {
locked_append(fl, start, end, mode, pthread_self());
rv = 1;
} else if (can_lock(fl, start, end, mode)) {
do_lock(fl, start, end, mode);
rv = 1;
} else {
/* the region is busy, we would lock */
rv = 0;
}
fl_unlock(fl);
return rv;
}
static void wait_on(filock_t *fl, off_t start, off_t end, int mode)
{
/* all waiter_ranges are created and destroyed here. A wr is born
* here, go to bed in the locking below, until wake_up() wakes us up
* and he dies. While it is manipulated several times outside this
* function, here is the only place where it's actually modified; it
* used to be allocated directly on the stack, but maybe some stuff
* assume thread stack is not touched by other threads and it could
* cause some problems in the future; remember: "better safe than
* sorry". */
struct waiter_range *wr;
wr = malloc(sizeof(struct waiter_range));
/* initialize wr */
wr->start = start;
wr->end = end;
wr->mode = mode;
wr->owner = pthread_self();
wr->next = NULL;
wr->prev = NULL;
sem_init(&(wr->sem), 0, 0);
/* add to the semi-circular list */
if (fl->waiters == NULL) {
wr->next = NULL;
wr->prev = wr;
fl->waiters = wr;
} else {
wr->next = NULL;
wr->prev = fl->waiters->prev;
fl->waiters->prev->next = wr;
fl->waiters->prev = wr;
}
fl_unlock(fl);
/* block until some other thread wakes us up */
while (sem_wait(&(wr->sem)) != 0)
/* it can fail with EINTR, retry */
;
if (sem_destroy(&(wr->sem)) != 0)
printd("ERROR IN DESTROY\n");
free(wr);
}
static void wake_up(filock_t *fl, off_t start, off_t end)
{
struct waiter_range *wr;
for (wr = fl->waiters; wr != NULL; wr = wr->next) {
if (!wr_range_overlaps(wr, start, end))
/* if the region doesn't overlap, we know beforehand
* the status couldn't have changed */
continue;
if (can_lock_tid(fl, wr->start, wr->end, wr->mode, wr->owner)) {
do_lock_tid(fl, wr->start, wr->end, wr->mode,
wr->owner);
/* remove from the semi-circular list */
if (fl->waiters == wr) {
/* head */
if (wr->next != NULL)
wr->next->prev = fl->waiters->prev;
fl->waiters = wr->next;
} else if (fl->waiters->prev == wr) {
/* tail */
wr->prev->next = NULL;
fl->waiters->prev = wr->prev;
} else {
/* middle */
wr->prev->next = wr->next;
wr->next->prev = wr->prev;
}
/* this will wake the thread up, which is blocked in
* wait_on(), and it will then free wr */
sem_post(&(wr->sem));
return;
}
}
/* nobody was waiting! */
return;
}
/* Get a lock, blocking until available */
int filo_lock(filock_t *fl, off_t start, off_t len, int mode)
{
off_t end = start + len - 1;
if (len <= 0)
return 0;
fl_lock(fl);
/* fast path for the uncontended case */
if (fl->locked == NULL) {
locked_append(fl, start, end, mode, pthread_self());
fl_unlock(fl);
} else if (region_free(fl, start, end)) {
locked_append(fl, start, end, mode, pthread_self());
fl_unlock(fl);
} else if (can_lock(fl, start, end, mode)) {
printd("locking\n");
do_lock(fl, start, end, mode);
fl_unlock(fl);
} else {
/* the region is busy, we wait */
wait_on(fl, start, end, mode);
/* when we return, fl->lock has already been unlocked, there's
* no need to release it */
}
printfl(fl);
return 1;
}
int filo_unlock(filock_t *fl, off_t start, off_t len)
{
struct locked_range *lr, *next;
off_t end = start + len - 1;
if (len <= 0)
return 0;
fl_lock(fl);
for (lr = fl->locked; lr != NULL; lr = next) {
next = lr->next;
if (!is_ours(lr))
continue;
if (!lr_range_overlaps(lr, start, end))
continue;
/* the range is ours and overlaps, unlock this area */
if (exclude_range(fl, lr, start, end) == 0) {
/* we need to remove lr */
if (fl->locked == lr)
fl->locked = lr->next;
if (lr->prev != NULL)
lr->prev->next = lr->next;
if (lr->next != NULL)
lr->next->prev = lr->prev;
free(lr);
}
}
wake_up(fl, start, end);
printd("UNLOCKED\n");
printfl(fl);
fl_unlock(fl);
return 1;
}
int filo_plockf(filock_t *fl, int cmd, off_t start, off_t len)
{
int rv, mode = 0;
off_t end = start + len - 1;
if (len <= 0)
return 0;
if (cmd & _FL_READ)
mode = FL_RD_MODE;
else if (cmd & _FL_WRITE)
mode = FL_WR_MODE;
if (cmd & _FL_LOCK)
rv = filo_lock(fl, start, len, mode);
else if (cmd & _FL_TLOCK)
rv = filo_trylock(fl, start, len, mode);
else if (cmd & _FL_ULOCK)
rv = filo_unlock(fl, start, end);
else
return -1;
if (rv == 0)
return -1;
return 0;
}